366 Find Leaves of Binary Tree

366. Find Leaves of Binary Tree

1. Question

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.
Example: Given binary tree
1
1
2
/ \
3
2 3
4
/ \
5
4 5
Copied!
Returns[4, 5, 3], [2], [1].
Explanation:
  1. 1.
    Removing the leaves[4, 5, 3]would result in this tree:
1
1
2
/
3
2
Copied!
  1. 1.
    Now removing the leaf[2]would result in this tree:
1
1
Copied!
  1. 1.
    Now removing the leaf[1]would result in the empty tree:
1
[]
Copied!
Returns[4, 5, 3], [2], [1].

2. Implementation

(1) DFS
思路: 对于每个node,找到它相应的高度,并根据这个高度加到相应的res里。leaves的那一层会在level 0。
1
class Solution {
2
public List<List<Integer>> findLeaves(TreeNode root) {
3
List<List<Integer>> res = new ArrayList<>();
4
recFindLeaves(root, res);
5
return res;
6
}
7
8
public int recFindLeaves(TreeNode node, List<List<Integer>> res) {
9
if (node == null) {
10
return 0;
11
}
12
13
int leftLevel = recFindLeaves(node.left, res);
14
int rightLevel = recFindLeaves(node.right, res);
15
int level = Math.max(leftLevel, rightLevel) + 1;
16
17
if (res.size() < level) {
18
res.add(new ArrayList<>());
19
}
20
res.get(level - 1).add(node.val);
21
return level;
22
}
23
}
Copied!

3. Time & Space Complexity

DFS: 时间复杂度: O(n), 空间复杂度: O(n)