Medium
这题思路很好,通过定义一个height来添加答案.Leaf node的height定义为0, 每远离Leaf一层就height加一. 这样我们就可以通过找到每个node的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<>();
height(root, res);
return res;
}
private int height(TreeNode node, List<List<Integer>> res){
if (node == null){
return -1;
}
int height = 1 + Math.max(height(node.left, res), height(node.right, res));
//height == 0, res.size() shoud be 1. if size() == 0 meaning haven't added this level
if (res.size() == height){
res.add(new ArrayList<>());
}
res.get(height).add(node.val);
return height;
}
}
可能不是很好看清楚recursion里面求height的同时也往res里再添加val, 画一个recursion tree方便理解具体过程.