LC107. 二叉树的层次遍历

[HealUP]

3.2 107. 二叉树的层次遍历

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        /*思路：
        1.广搜得到二维数组的结果
        2.将二维数组反转
         */
        //创建一个结果二维数组
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return res;
        }
        que.offer(root);//根节点放入队列
        while (!que.isEmpty()) {
            //创建一维数组保存当前层的节点
            List<Integer> list = new ArrayList<>();
            //保存当前层的节点的数量
            int len = que.size();
            for (int i = 0; i < len; i++) {
                //保存当前出队的节点
                TreeNode node = que.poll();
                //将其值存入到一维数组
                list.add(node.val);
                //将该节点的左右节点入队
                if (node.left != null) que.offer(node.left);//空节点不入队
                if (node.right != null) que.offer(node.right);
            }
            //将该层的节点的值存放到一维数组中
            res.add(list);
        }
        //开辟一个二维数组的空间，存放反转后的二维数组的结果
        List<List<Integer>> result = new ArrayList<>();
        for (int i = res.size() - 1; i >= 0; i--) {//数组下标从0开始，最大长度是数组大小减1
            result.add(res.get(i));//get获取对应位置的元素
        }

        //返回结果
        return result;
    }
}