【递归, DFS】寻找二叉树的叶子节点

题目

366. 寻找二叉树的叶子节点

---

给你一棵二叉树，请按以下要求的顺序收集它的全部节点：

• 依次从左到右，每次收集并删除所有的叶子节点
• 重复如上过程直到整棵树为空

示例:

输入: [1,2,3,4,5]

          1
         / \
        2   3
       / \     
      4   5    

输出: [[4,5,3],[2],[1]]

解释:

1. 删除叶子节点 [4,5,3] ，得到如下树结构：

          1
         / 
        2          

2. 现在删去叶子节点 [2] ，得到如下树结构：

          1          

3. 现在删去叶子节点 [1] ，得到空树：

          []         

解题

方法一：递归 DFS 后序遍历

思路

深度优先遍历整棵树，遍历到叶子节点的时候开始从0计算层数，往回推的时候把两个子节点的层数最大值拿出来作为当前层数，把节点加入对应层然后返回当前层数+1。

代码

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> findLeaves(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int level = Math.max(dfs(root.left), dfs(root.right));
        if (level == ans.size()) ans.add(new ArrayList<>());
        ans.get(level).add(root.val);
        return level + 1;
    }
}