LC 366 Find Leaves of Binary Tree(M)

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

public List<List<Integer>> findLeaves(TreeNode root)

边界条件 递归调用，如果当前是null， 返回-1,这样上面的叶子节点的index就为0。

解题思路 Recursive DFS

这道题换句话说就是找每个node的index，这个index就是最后结果中这个节点所在的list的index，比如4,5,3的index是0， 2的index是1，1的index是2. 怎么找呢？二分，看左，看右。 确定一个点的index，得知道他的左孩子index是多少，右孩子的index是多少，当前这个点的index是他左右孩子的index最大值+1，这可以很容易地观察得到。比如对于1来说，左孩子2的index是1，右孩子3的index是0，那1的index肯定是max(1, 0) + 1，即2.

public List<List<Integer>> findLeaves(TreeNode root){
      List<List<Integer>> result = new ArrayList<List>();
      helper(result, root);
}
public int helper(List<List<Integer>> result, root){
      if(root == null)
            return -1; //保证叶子的index是 0
      int left = helper(result, root.left);
      int right = helper(result, root.right);
      int cur = Math.max(left, right) + 1;
      if(result.size() == cur){ //一定是从 index 0 数组开始
            result.add(new ArrayList<Integer>());
      }
      result.get(cur).add(root.value);
      return result;
}