32-从上到下打印二叉树

从上到下打印二叉树(简单)

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

比如如下的二叉树，返回[3,9,20,15,7]

需要保证同一层的从左到右打印，那么可以使用先进先出的队列。

• 先将根节点放到队列
• 假如队列不为空，则弹出队头元素，然后将左节点和右节点依次入队，这样依然保持顺序。

public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        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);
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();

    }

从上到下打印二叉树(增大难度)

题目基本一样，但是返回需要按照一行一行的返回。

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

比如如下的二叉树，返回

[

[3],

[9,20],

[15,7]

]

这次需要明确的分层打印，关键就是如何确定层。

第一种 偷梁换柱大法

public List<List<Integer>> levelOrder2(TreeNode root) {
        if (root == null) {
            return  null;
        }
        Queue<TreeNode> first = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        first.add(root);
        while (!first.isEmpty()) {
            List<Integer> one = new ArrayList<>();
            Queue<TreeNode> second = new LinkedList<>();//临时队列
            while (!first.isEmpty()) {
                TreeNode node = first.poll();
                one.add(node.val);
                //将下一层的放到second里
                if (node.left != null) {
                    second.add(node.left);
                }
                if (node.right != null) {
                    second.add(node.right);
                }
            }
            result.add(one);
            first = second;//瞒天过海 偷梁换柱
        }
        return result;
    }

第二种 记录一层的数量

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if(root == null){
            return out;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();//记录这一层有多少个节点
            List<Integer> cur = new ArrayList<>();
            for(int i = 0; i < size; i++){ //将这一层的节点遍历完
                TreeNode node = queue.remove();
                cur.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            out.add(cur);
        }
        return out;
    }

从上到下打印二叉树(继续增大难度)

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

比如如下的二叉树，返回

[

[3],

[20,9],

[15,7]

]

需要增加一个记录打印顺序的标志位。

 if (root == null) {
            return Collections.emptyList();
        }
        LinkedList<TreeNode> first = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        first.add(root);
        boolean left2Right = true;
        while (!first.isEmpty()) {
            List<Integer> one = new ArrayList<>();
            LinkedList<TreeNode> second = new LinkedList<>();
            while (!first.isEmpty()) {
                TreeNode node = null;
                int size = first.size();
                //调整打印顺序
                if (left2Right) {
                    for (int i = 0; i < size; i++) {
                        one.add(first.get(i).val);
                    }
                }else{
                    for (int i = size; i >= 0; i--) {
                        one.add(first.get(i).val);
                    }
                }
                //依照从左到右的顺序放入队列
                while (!first.isEmpty()) {
                    node = first.poll();
                    if (node.left != null) {
                        second.add(node.left);
                    }
                    if (node.right != null) {
                        second.add(node.right);
                    }
                }
            }
            result.add(one);
            first = second;
            left2Right = !left2Right;
        }
        return result;

进一步优化，可以反转每一次的数据即可。

public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) {
            queue.add(root);
        }
        boolean left2Right = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> one = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                one.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            
            if(!left2Right){
              //反转单层数据即可
                Collections.reverse(one);
            }
            result.add(one);
            left2Right = !left2Right;
        }
        return result;
    }