Given the root of a binary tree, collect a tree's nodes as if you were doing this:
Collect all the leaf nodes.
Remove all the leaf nodes.
Repeat until the tree is empty.
Example 1:
**Input:** root = [1,2,3,4,5]
**Output:** [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.
Example 2:
**Input:** root = [1]
**Output:** [[1]]
Constraints:
The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100
ac
/**
* 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) {
Map<Integer, List<Integer>> map = new HashMap<>();
dfs(root, map);
List<List<Integer>> res = new ArrayList<>();
for (int i = 1; i <= map.size(); i++) {
res.add(map.get(i));
}
return res;
}
public int dfs(TreeNode node, Map<Integer, List<Integer>> map) {
if (node == null) return 0;
int left = dfs(node.left, map);
int right = dfs(node.right, map);
int dist = Math.max(left, right) + 1;
map.putIfAbsent(dist, new ArrayList<>());
map.get(dist).add(node.val);
return dist;
}
}
/*
1) dfs get distance to leaf, store in map; 2) iterate map, get result
*/
