跃迁引擎

空気を読んだ雨降らないでよ

iOS Research & Development


从上到下打印二叉树

剑指 Offer 32 - II. 从上到下打印二叉树 II

题目

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

1
2
3
4
5
[
[3],
[9,20],
[15,7]
]

提示:

节点总数 <= 1000

题解

这一题不能被题目描述迷惑,误认为是道顺序遍历题,所有二叉树的题基本都逃不过递归,几乎都可以用递归来解,所以本题的思路也是如此。

既然题目要求自上而下打印,那么我们就自上而下递归,保留层层节点即可,最终再一起输出就可以满足题目要求:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> nodes = new ArrayList(); // 节点数组,用于保存节点的值
public List<List<Integer>> levelOrder(TreeNode root) {
// 从根节点开始向下遍历
traverse(root, 0);
return nodes;
}

private void traverse(TreeNode root, int k) {
// 如果不到树的底部就一直递归遍历下去
if (root != null) {
// 节点数组长度小于等于k, k在这里表示数的层级深度
if (nodes.size() <= k) {
// 向节点数组中添加一个新的二维数组作为占位,也就是开辟新的一层数组空间,用于储存新一层深度的节点
List<Integer> subNodes = new ArrayList();
nodes.add(subNodes);
}
// 将该层根节点(当前节点)的值添加到节点数组中
nodes.get(k).add(root.val);
// 由于有输出顺序要求,所以先递归遍历左子节点及其子树,层级每层加1(因为是子节点,所以层级深度加1)
// 注意:此处k + 1不能写成 k++,因为 k++ 等价于 k = k + 1,相当于给k本身赋值了,这样会干扰后面右子节点的递归结果
traverse(root.left, k + 1);
// 递归遍历右子节点及其子树,同上
traverse(root.right, k + 1);
}
}
}
最近的文章

二叉搜索树的第k大节点

剑指 Offer 54. 二叉搜索树的第k大节点 …

, , , , 开始阅读
更早的文章

二叉树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先 …

, , 开始阅读
comments powered by Disqus