从上往下打印二叉树

题目描述

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

题解

不像前、中、后序遍历，它要求一层一层地遍历

利用一个辅助队列，弹出父节点的同时，将它的左右孩子加入队列

时间复杂度: O(N)- 空间复杂度: O(N)

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    if (root == null)
        return res;

    Deque<TreeNode> deque = new LinkedList<>();
    deque.add(root);
    while (!deque.isEmpty()){
        TreeNode node = deque.pop();
        res.add(node.val);

        if (node.left != null)
            deque.add(node.left);
        if (node.right != null)
            deque.add(node.right);
    }
    return res;
}