【剑指Offer】从上往下打印二叉树

Posted on | In ,

题目

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

实现

1
2
3
4
5
6
7
8
9
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();

    if (root == null)
        return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()){
        TreeNode node = queue.poll();
        result.add(node.val);

        if (node.left != null)
            queue.offer(node.left);

        if (node.right != null)
            queue.offer(node.right);
    }

    return result;
}

相关题目

如何广度优先遍历一个有向图》这同样也可以基于队列实现。树是图的一种特殊退化形式，从上到下按层遍历二叉树，从本质上来说就是广度优先遍历二叉树。