05 August 2008
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:
Input: [1,2,3,4,5]
1
2
3
4
5
1
/ \
2 3
/ \
4 5
Output: [[4,5,3],[2],[1]]
Explanation:
Removing the leaves [4,5,3] would result in this tree:
1
2
3
1
/
2
Now removing the leaf [2] would result in this tree:
1
1
Now removing the leaf [1] would result in the empty tree:
1
[]
[[3,5,4],[2],[1]], [[3,4,5],[2],[1]], etc, are also consider correct answers since per each level it doesn’t matter the order on which elements are returned.
使用dfs，递归时传入上一个节点，如果当前节点是叶子节点，则将值加入集合，使用上个节点将当前叶子节点删除。每递归一次就会修剪掉叶子节点，形成新树，循环修剪叶子节点，直至只剩下根节点，最后将根节点加入结果集。
递归的思想不要一个元素一个元素或者一层一层的角度去想，而是把返回条件写好后，直接考虑左子树和右子树的关系即可，不要想太复杂。
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
37
38
39
40
41
42
43
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
while (root != null) {
List<Integer> oneLevel = new ArrayList<>();
// 每一层的更新让递归栈来保存 该层叶子节点和当前oneLevel数组的信息，每个oneLevel对应的叶子节点都是最外层
root = dfs(root, oneLevel);
results.add(oneLevel);
}
return results;
}
private TreeNode dfs(TreeNode node, List<Integer> oneLevel) {
if (node == null) { // 寻找叶子节点过程中的base case，比如只有左子树或者只有右子树为空
return null;
}
if (node.left == null && node.right == null) { // 叶子节点
oneLevel.add(node.val);
return null; // 叶子节点加入list后，从该层返回
}
// 递归检查左右子树，它们有自己对应的oneLevel和递归参数在递归栈中
node.left = dfs(node.left, oneLevel);
node.right = dfs(node.right, oneLevel);
return node;
}
}