面试题32_I_从上到下打印二叉树.md

面试题 32_I ：从上到下打印二叉树

---

leetcode-cn 题目地址

📗difficulty：Easy

• 树
• 广度优先搜索

---

1. 题目描述📃

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

样例 1 ：

	3
   / \
  9  20
    /  \
   15   7

返回：

[3,9,20,15,7]

注意：

• 节点总数 <= 1000

---

2. 解题思路💡

树的层序遍历，也可以看成是 图 的 广度优先搜索。

代码实现

public int[] levelOrder(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    Deque<TreeNode> deque = new LinkedList<>();
    deque.offerLast(root);
    while (deque.peekFirst() != null) {
        TreeNode cur = deque.pollFirst();
        if (cur != null) {
            res.add(cur.val);
            if (cur.left != null) {
                deque.offerLast(cur.left);
            }

            if (cur.right != null) {
                deque.offerLast(cur.right);
            }
        }
    }
    int[] ans = new int[res.size()];
    int idx = 0;
    for (int num : res) {
        ans[idx++] = num;
    }
    return ans;
}

复杂度分析

• 时间复杂度：O(n) 。每个节点都访问一遍。
• 空间复杂度：O(n) 。最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 O(N) 大小的额外空间。

---

3. 总结🎯

相似题目

面试题32 - II. 从上到下打印二叉树 II

面试题32 - III. 从上到下打印二叉树 III