LeetCode 从上到下打印二叉树-一一网

这是我参与更文挑战的第 25 天，活动详情查看：更文挑战

从上到下打印二叉树（剑指 Offer32-1）

题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7]

示例 1：

[3,9,20,15,7]
复制代码

提示

节点总数 <= 1000

思路分析

从上到下打印二叉树，我们可以通过一个队列去不断遍历，一开始将第一层的节点放到该队列中，然后遍历这个队列中的节点，可以得到第二层的所有节点，并且将这些节点放到队列中，之后再遍历这一层的节点，我们就可以得到第三层的所有节点，之后继续遍历队列中的所有节点，我们就可以打印第四层的节点，这样不断的遍历，得到所有的节点。最后我们在遍历这些节点，将其放到数组中，并返回。

代码展示

解法一：

public int[] levelOrder(TreeNode root) {
        if(root == null){
            return new int[0];
        }
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            result.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        int[] arr = new int[result.size()];
        for(int i = 0;i < result.size();i++){
            arr[i] = result.get(i);
        }
        return arr;
    }
复制代码

从上到下打印二叉树（剑指 Offer32-3）

题目描述

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

示例 1：

返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
]
复制代码

提示

节点总数 <= 1000

思路分析

这道题和上面那道题很相似，只不过需要返回的是一个二维数组，从上到下打印二叉树，我们可以通过一个队列去不断遍历，一开始将第一层的节点放到该队列中，然后遍历这个队列中的节点，可以得到第二层的所有节点，并且将这些节点放到队列中，之后再遍历这一层的节点，我们就可以得到第三层的所有节点，之后继续遍历队列中的所有节点，我们就可以打印第四层的节点，这样不断的遍历，得到所有的节点。最后我们在遍历这些节点，将其放到数组中，并返回。

同时打印使用之字形打印每一层的节点，这个时候我们需要在每次遍历节点的做下处理，提前获取遍历队列的大小，然后放大二维数组的某一项中，之字形打印我们使用奇数和偶数进行判断。

代码展示

解法一：

public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int deep = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> innerList = new ArrayList<>();
            if(deep % 2 != 0){
                for(int i = 0;i < size;i++){
                    TreeNode node = queue.poll();
                    innerList.add(node.val);
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }
            } else {
                for(int i = 0;i < size;i++){
                    TreeNode node = queue.poll();
                    innerList.add(0,node.val);
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }
            }
            deep++;
            result.add(innerList);
        }
        return result;

    }
复制代码