题目描述

对一个二叉树，收集这个二叉树的叶子结点后，去掉这些叶子节点，重复这个步骤直到树为空。返回一个二维数组，数组的第一维表示上述步骤需重复几次后，该结点成为叶子节点。

样例

input
          1
         / \
        2   3
       / \     
      4   5  

output [[4, 5, 3], [2], [1]]

第一次去掉[4, 5, 3]这三个叶子结点，二叉树变为
          1
         / 
        2    

第二次去掉[2]这一个叶子结点，二叉树变为
           1
第三次去掉[1]这一个叶子节点，二叉树为空，结束。

最后返回[[4, 5, 3], [2], [1]]

算法

后序遍历

按照左右根的顺序递归，每次递归返回当前结点到最远的叶子结点的路径长度。当前结点到最远的叶子结点的路径长度k=max(left, right)+1，k为当前结点应该加入的二维数组的第一维下标

时间复杂度分析：每个结点只访问一次 O(n)

Java 代码

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> list  = new ArrayList<>();
        dfs(list, root);
        return list;
    }

    public int dfs(List<List<Integer>> list, TreeNode node) {
        if(node==null) return -1;
        int left = dfs(list, node.left);
        int right= dfs(list, node.right);
        int k = Math.max(left, right)+1;
        if(list.size()<k+1) list.add(new ArrayList<>());
        list.get(k).add(node.val);
        return k;
    }
}