题解 | #从上往下打印二叉树#

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。
示例1
输入：{5,4,#,3,#,2,#,1}
返回值：[5,4,3,2,1]

题目分析

要求二叉树“从上往下”打印（即按层打印），又称为二叉树的广度优先搜索（BFS）。
如示例1：{5,4,#,3,#,2,#,1}

从上往下遍历结果为：5,4,3,2,1

解题思路

树的BFS遍历通常使用“队列”的先入先出特性来实现
1.将头结点放入队列中；
2.从队列头中取出一个结点，将这个结点的值放入遍历结果list中，且将它不为空的子节点依次放到队尾（这样可以保证子节点的访问顺序是从左到右）；
3.重复2，直到队列为空，即二叉树遍历完成。
具体过程如下图：例子{5,4,3,#,2,1,#}

代码实现

public ArrayList<integer> PrintFromTopToBottom(TreeNode root) {
        // 存储结果
        ArrayList<integer> result = new ArrayList<integer>();
        if(root == null) return result;
        // 借助队列，保存数据，广度遍历树
        Queue<treenode> queue = new LinkedList<treenode>();
        // 1.放入头结点
        queue.offer(root);
        while(!queue.isEmpty()){
            // 2.取出队列头部结点
            TreeNode temp = queue.poll();
            if(temp.left != null){
                // 3.结点左节点不为空，放入队列尾部
                queue.offer(temp.left);
            }
            if(temp.right != null){
                // 4.结点右节点不为空，放入队列尾部
                queue.offer(temp.right);
            }
            // 5.获得结点值
            result.add(temp.val);
        }
        return result;
    }

时间复杂度：O(N)，需要遍历整个树；
空间复杂度：队列中存储的子节点最多为N/2（平衡树），O(N)；

扩展

若是要求打印结果，同层要从右往左打印，应该如何修改实现？
答：只要在判断结点的左右子节点是否为空的情况下，先判断右节点，再判断左节点，则同一层的结点访问顺序为“从右到左”。