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-解题思路分析/