Medium
这道题终于在第五次做的时候，明白了Binary Tree的Height和Depth的区别，Height是从下往上数，Leaf的height为0， Root的height最大；而Depth是从上往下数，root的depth为0， Leaf的depth最高。所以这道题说是Find leaves, 其实是把所有node按Height分，比如第一层所有的Leaf nodes就是height = 0的node; 第二层的Leaf nodes就是height = 1的node; 第三层的leaf nodes就是height = 3的nodes。 这样发现这个问题其实只和height有关，就很好解决了。
/**
* 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>> res = new ArrayList<>();
if (root == null){
return res;
}
helper(res, root);
return res;
}
//搞清楚树的height和depth的区别
private int helper(List<List<Integer>> res, TreeNode root){
if (root == null){
return -1;
}
int left = helper(res, root.left);
int right = helper(res, root.right);
int height = Math.max(left, right) + 1;
//if we have height 0, size should be 1; if we have height 1, size should be 2.
//so if we do have each level in res, height should be one less than size.
//However if height == size, meaning we don't have that level yet.
if (height == res.size()){
res.add(new ArrayList<Integer>());
}
res.get(height).add(root.val);
return height;
}
}
