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, 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].

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩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;

    }

}