从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
解题思路:
从上至下按层打印,明显是二叉树的层序遍历,可以借助队列来实现。
代码:
public int[] levelOrder(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
ans.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
int[] arr = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) {
arr[i] = ans.get(i);
}
return arr;
}
复杂度分析
- 时间复杂度$O(N)$:$N$ 为二叉树的节点总数。
- 空间复杂度$O(N)$:最差情况下,即当树为平衡二叉树时,最多有 $\frac{2}$ 个树节点同时在
queue
中,使用 $O(N)$ 大小的额外空间。
评论区