【2022-08-17每日一题】1302. 层数最深叶子节点的和

2022-08-17每日一题：1302. 层数最深叶子节点的和

• 难度：Medium
• 标签：树 、 深度优先搜索 、 广度优先搜索 、 二叉树

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

示例 1：

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

示例 2：

输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出：19

提示：

• 树中节点数目在范围 [1, 104] 之间。
• 1 <= Node.val <= 100

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deepestLeavesSum(root *TreeNode) (ans int) {
    if root == nil {
        return ans
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        ans = 0
        for n := len(queue); n > 0; n-- {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            ans += node.Val
        }
    }
	return ans
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方法二：DFS（深度优先遍历）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deepestLeavesSum(root *TreeNode) (sum int) {
    maxLevel := 0
    var dfs func(root *TreeNode, level int)
    dfs = func(root *TreeNode, level int) {
        if root == nil {
            return
        }
        if level > maxLevel {
            sum, maxLevel = root.Val, level
        } else if level == maxLevel {
            sum += root.Val
        }
        dfs(root.Left, level + 1)
        dfs(root.Right, level + 1)
    }
    dfs(root, 0)
    return sum
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

LeetCode题库地址

• https://leetcode.cn/problems/deepest-leaves-sum