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定義成從最深的子節(jié)點到自己的距離乖坠，那么所有最外層節(jié)點的depth都是0，次外層節(jié)點的depth為1萍膛，以此類推绑洛。
起先用的是HashMap + PriorityQueue的解法庐橙，后來發(fā)現(xiàn)并不需要悼粮，用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;
}
}
