Description
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
tree
Returns [4, 5, 3], [2], [1].
Explanation:
1. Removing the leaves [4, 5, 3] would result in this tree:
image.png
2. Now removing the leaf [2] would result in this tree:
image.png
3. Now removing the leaf [1] would result in the empty tree:
image.png
Returns [4, 5, 3], [2], [1].
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
Solution
DFS, time O(n), space O(n)
利用Depth辅助即可。depth定义成从最深的子节点到自己的距离，那么所有最外层节点的depth都是0，次外层节点的depth为1，以此类推。
起先用的是HashMap + PriorityQueue的解法，后来发现并不需要，用List<List<Integer>>即可，因为一定是从外到里添加到结果集，顺序不会被打乱。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> leaves = new ArrayList<>();
getDepth(root, leaves);
return leaves;
}
private int getDepth(TreeNode root, List<List<Integer>> leaves) {
if (root == null) {
return -1;
}
int depth = Math.max(getDepth(root.left, leaves)
, getDepth(root.right, leaves)) + 1;
if (leaves.size() < depth + 1) {
leaves.add(new ArrayList<>());
}
leaves.get(depth).add(root.val);
return depth;
}
}
