【二叉树打卡2】从上往下打印二叉树

【题目】

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

【难度】

易

解答

这个像相当于二叉树四种遍历中的层序遍历了，其思想是采用广度优先遍历，借助一个辅助队列，步骤如下：

1、把二叉树的根节点 root 放进队列。

2、如果队列不为空，取出队列的一个节点，把这个节点的左右孩子放进队列中(为空的话就不用放)，然后打印这个节点。

3、一直重复步骤 2 ，直到队列为空，此时遍历结束，代码如下：

代码如下：

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null)
            return list;
        // 根放入队列
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node =  queue.poll();
            list.add(node.val);
            if(node.left != null)
                queue.offer(node.left);
            if(node.right != null)
                queue.offer(node.right);
        }
        return list;
    }

二叉树的遍历中，有先序遍历、中序遍历、后续遍历，不过，如果你采用递归来做的话都比较简单，所以，我是建议，大家都要学会，不使用递归来做这三种遍历，而是利用利用队列和栈来辅助，进而在一个while循环中就能够进行这三种遍历了。

往期