侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-18 / 0 评论 / 0 点赞 / 109 阅读 / 311 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


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

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

示例:

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

          1
         / \
        2   3
       / \     
      4   5    

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

解释:

  1. 删除叶子节点 [4,5,3] ,得到如下树结构:
          1
         / 
        2          
  1. 现在删去叶子节点 [2] ,得到如下树结构:
          1          
  1. 现在删去叶子节点 [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;
    }
}
0

评论区