Leetcode/LinkedIn -- 366. Find Leaves of Binary Tree - dfs

366. Find Leaves of Binary Tree - dfs

• Difficulty: Medium

https://leetcode.com/problems/find-leaves-of-binary-tree/

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 

          1
         / \
        2   3
       / \     
      4   5    

Returns [4, 5, 3], [2], [1].

Explanation:

1. Removing the leaves [4, 5, 3] would result in this tree:

          1
         / 
        2          

2. Now removing the leaf [2] would result in this tree:

          1          

3. Now removing the leaf [1] would result in the empty tree:

          []         

Returns [4, 5, 3], [2], [1].

思路分析：https://discuss.leetcode.com/topic/49194/10-lines-simple-java-solution-using-recursion-with-explanation

 注意点：当前node的高度是 1 + Max（height(node.left),height(node.right)）。leaf的高度是0

             The height of a node is also the its index in the result list (res).

关键字：dfs(recurrsion)

public class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(root,res);
        return res;
    }
    public int dfs(TreeNode root,List<List<Integer>> res){
        if(root==null){ return -1;}
        int height = 1+Math.max(dfs(root.left,res),dfs(root.right,res));
        if(res.size()<height+1) res.add(new ArrayList<Integer>());//if(arr.get(height)==null) will give error
        res.get(height).add(root.val);
        return height;
    }
}