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
| class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> findLeaves(TreeNode root) {
TreeNode dummy = new TreeNode(0, root, null);
while (dummy.left != null || dummy.right != null) {
ans.add(new ArrayList<>());
dfs(dummy);
}
return ans;
}
private boolean dfs(TreeNode node) {
if (node == null) {
return false;
}
if (node.left == null && node.right == null) {
ans.get(ans.size() - 1).add(node.val);
return true;
}
boolean isLeftLeaf = dfs(node.left);
if (isLeftLeaf) {
node.left = null;
}
boolean isRightLeaf = dfs(node.right);
if (isRightLeaf) {
node.right = null;
}
return false;
}
}
|
最常规的做法, 就是一遍遍把leaf给剪掉即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> findLeaves(TreeNode root) {
getHeight(root);
return ans;
}
private int getHeight(TreeNode node) {
if (node == null) {
return -1;
}
int currHeight = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
if (currHeight == ans.size()) {
ans.add(new ArrayList<>());
}
ans.get(currHeight).add(node.val);
return currHeight;
}
}
|
这个解法最绝. 就是看每个node的height是多少. 我们求height的话是从低到高求的, 因此第一次得到答案的一定是leaf node, 然后leaf node之上…于是我们就看每次到的height的值和ans的size的大小, 如果二者相等, 这就说明这个height是第一次来, 我们就要在ans中加ArrayList, 然后把我们自己添加进来. 如果height小于size大小, 那就说明这个height之前来过, 我们直接访问这个height对应的list把自己加进来即可. 由于我们是从下到上递归返回, 因此height是一点一点增加的. 不可能某个height没达到, 就突然网上跃迁到另一个更高的height.
时间复杂度: O(n) n是node的个数.
空间复杂度: O(n) n是node的个数.
