LEETCODE 1302. Deepest Leaves Sum 解题思路分析

题目大意:

层数最深叶子节点的和

给你一棵二叉树,请你返回层数最深的叶子节点的和。

示例:

输入:root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出:15

提示:

  • 树中节点数目在 1 到 10^4 之间。
  • 每个节点的值在 1 到 100 之间。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1302

解题思路分析:

由于题目求的是最深层叶子节点的值之和,因此我们应该先计算出二叉树最大层数。取得层数之后,我们可以使用dfs找到每个叶子节点,如果该叶子节点的层数等于最大层数,将该节点的值累加到返回结果即可。

实现代码:

public int deepestLeavesSum(TreeNode root) {
    int maxDeep = getDeep(root, 0); // 取得最大层数
    return sum(root, 0, maxDeep); // 累加最大层数所有叶子节点的值
}

int getDeep(TreeNode root, int deep){
    if(root.left==null&&root.right==null) return deep;
    int leftDeep=root.left== null?deep:getDeep(root.left, deep+1);
    int rightDeep=root.right== null?deep:getDeep(root.right, deep+1);
    return Math.max(leftDeep,rightDeep);
}

int sum(TreeNode root, int deep, int maxDeep){
    if(root.left==null&&root.right==null){
        return deep==maxDeep?root.val:0;
    }
    int sumL= root.left!=null?sum(root.left,deep+1,maxDeep):0;
    int sumR=root.right!=null?sum(root.right,deep+1,maxDeep):0;
    return sumL+sumR;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.84% of Java online submissions for Deepest Leaves Sum.

Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Deepest Leaves Sum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1302-deepest-leaves-sum-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

LEETCODE 1302. Deepest Leaves Sum 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上) - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。