366. 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,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,[1].

?[暴力解法]：

时间分析：

空间分析：

?[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

root为空

［思维问题］：

没看出来是dc-depth的题，详见此图，请理解：

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

［输入量］：空：?正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

?

1. res.get(level).add(node.val);可以实现精确添加，指定哪一层添加哪个数?

［二刷］：

双层数组的添加，直接.add(new ArrayList<>());就行了 不需要指定名字

helper(result,root); int函数调用的时候可以没有返回值，直接用

?

［三刷］：

［四刷］：

［五刷］：

? [五分钟肉眼debug的结果]：

［总结］：

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

?[代码风格] ：

?[是否头一次写此类driver funcion的代码] ：

?[潜台词] ：

?

/**
 * 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) {
        //ini
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        //cc
        if (root == null) return result;
        
        //call the helper function 
        depthHelper(result,root);
        
        //return
        return result;
    }
    
    public int depthHelper(List<List<Integer>> result,TreeNode root) {
        //cc: root == null
        if (root == null) return -1;
        
        //get depth
        int depth = 1 + Math.max(depthHelper(result,root.left),depthHelper(result,root.right));
        
        if (depth + 1 >  result.size()) result.add(new ArrayList<Integer>());
        
        //add root.val
        result.get(depth).add(root.val);
        
        return depth;
    }
}