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方便理解具體過程.
image.png
