leetcode地址：層數最深葉子節點的和
給你一棵二叉樹的根節點 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

實現思路

廣度優先搜索（BFS）：

使用隊列進行層次遍歷，逐層掃描樹。
每次進入新的一層時，重置當前層的和。
記錄當前層的葉子節點和，直到遍歷完整棵樹。
深度優先搜索（DFS）：

使用遞歸方法，記錄每個節點的層數。
通過遞歸遍歷樹，更新當前層數和最深層葉子節點和。
返回最深層葉子節點和。

代碼詳解

廣度優先搜索（BFS）
使用廣度優先搜索（BFS）遍歷樹，每次進入新的一層時，重置當前層的和，并累加當前層的葉子節點值，直到遍歷完整棵樹。

from collections import deque# 定義二叉樹節點類
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# BFS方法返回層數最深的葉子節點的和
def deepestLeavesSumBFS(root):if not root:return 0queue = deque([root])while queue:level_sum = 0for _ in range(len(queue)):node = queue.popleft()level_sum += node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)return level_sum# 測試示例
if __name__ == "__main__":# 創建測試二叉樹#        1#       / \#      2   3#     / \   \#    4   5   6#   /       / \#  7       8   9root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)root.right.right = TreeNode(6)root.left.left.left = TreeNode(7)root.right.right.left = TreeNode(8)root.right.right.right = TreeNode(9)result = deepestLeavesSumBFS(root)print("層數最深的葉子節點的和 (BFS):", result)  # 應該輸出24

深度優先搜索（DFS）
使用深度優先搜索（DFS）遍歷樹，記錄每個節點的層數。通過遞歸遍歷樹，更新當前層數和最深層葉子節點和。

# 定義二叉樹節點類
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# DFS方法返回層數最深的葉子節點的和
def deepestLeavesSumDFS(root):if not root:return 0max_depth = -1sum_at_max_depth = 0def dfs(node, depth):nonlocal max_depth, sum_at_max_depthif not node:return# 如果是葉子節點if not node.left and not node.right:if depth > max_depth:max_depth = depthsum_at_max_depth = node.valelif depth == max_depth:sum_at_max_depth += node.valelse:dfs(node.left, depth + 1)dfs(node.right, depth + 1)dfs(root, 0)return sum_at_max_depth# 測試示例
if __name__ == "__main__":# 創建測試二叉樹#        1#       / \#      2   3#     / \   \#    4   5   6#   /       / \#  7       8   9root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)root.right.right = TreeNode(6)root.left.left.left = TreeNode(7)root.right.right.left = TreeNode(8)root.right.right.right = TreeNode(9)result = deepestLeavesSumDFS(root)print("層數最深的葉子節點的和 (DFS):", result)  # 應該輸出24

go實現

廣度優先搜索（BFS）

package mainimport ("fmt"
)// TreeNode 定義二叉樹節點
type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}// deepestLeavesSumBFS 使用廣度優先搜索（BFS）返回層數最深的葉子節點的和
func deepestLeavesSumBFS(root *TreeNode) int {if root == nil {return 0}queue := []*TreeNode{root}var levelSum intfor len(queue) > 0 {levelSum = 0qLen := len(queue)for i := 0; i < qLen; i++ {node := queue[0]queue = queue[1:]levelSum += node.Valif node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}}return levelSum
}// 測試示例
func main() {// 創建測試二叉樹//        1//       / \//      2   3//     / \   \//    4   5   6//   /       / \//  7       8   9root := &TreeNode{Val: 1}root.Left = &TreeNode{Val: 2}root.Right = &TreeNode{Val: 3}root.Left.Left = &TreeNode{Val: 4}root.Left.Right = &TreeNode{Val: 5}root.Right.Right = &TreeNode{Val: 6}root.Left.Left.Left = &TreeNode{Val: 7}root.Right.Right.Left = &TreeNode{Val: 8}root.Right.Right.Right = &TreeNode{Val: 9}result := deepestLeavesSumBFS(root)fmt.Printf("層數最深的葉子節點的和 (BFS): %d\n", result) // 應該輸出24
}

深度優先搜索（DFS）

package mainimport ("fmt"
)// TreeNode 定義二叉樹節點
type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}// deepestLeavesSumDFS 使用深度優先搜索（DFS）返回層數最深的葉子節點的和
func deepestLeavesSumDFS(root *TreeNode) int {if root == nil {return 0}var maxDepth intvar sumAtMaxDepth intvar dfs func(node *TreeNode, depth int)dfs = func(node *TreeNode, depth int) {if node == nil {return}// 如果是葉子節點if node.Left == nil && node.Right == nil {if depth > maxDepth {maxDepth = depthsumAtMaxDepth = node.Val} else if depth == maxDepth {sumAtMaxDepth += node.Val}} else {dfs(node.Left, depth+1)dfs(node.Right, depth+1)}}dfs(root, 0)return sumAtMaxDepth
}// 測試示例
func main() {// 創建測試二叉樹//        1//       / \//      2   3//     / \   \//    4   5   6//   /       / \//  7       8   9root := &TreeNode{Val: 1}root.Left = &TreeNode{Val: 2}root.Right = &TreeNode{Val: 3}root.Left.Left = &TreeNode{Val: 4}root.Left.Right = &TreeNode{Val: 5}root.Right.Right = &TreeNode{Val: 6}root.Left.Left.Left = &TreeNode{Val: 7}root.Right.Right.Left = &TreeNode{Val: 8}root.Right.Right.Right = &TreeNode{Val: 9}result := deepestLeavesSumDFS(root)fmt.Printf("層數最深的葉子節點的和 (DFS): %d\n", result) // 應該輸出24
}

Kotlin實現

廣度優先搜索（BFS）

import java.util.LinkedList
import java.util.Queue// 定義二叉樹節點類
class TreeNode(var `val`: Int) {var left: TreeNode? = nullvar right: TreeNode? = null
}// BFS方法返回層數最深的葉子節點的和
fun deepestLeavesSumBFS(root: TreeNode?): Int {if (root == null) return 0var sum = 0val queue: Queue<TreeNode> = LinkedList()queue.add(root)// 廣度優先搜索（BFS）while (queue.isNotEmpty()) {sum = 0 // 重置當前層的和val size = queue.sizefor (i in 0 until size) {val node = queue.poll()sum += node.`val` // 累加當前層節點的值// 將左右子節點加入隊列node.left?.let { queue.add(it) }node.right?.let { queue.add(it) }}}return sum
}// 測試示例
fun main() {// 創建測試二叉樹//        1//       / \//      2   3//     / \   \//    4   5   6//   /       / \//  7       8   9val root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left?.left = TreeNode(4)root.left?.right = TreeNode(5)root.right?.right = TreeNode(6)root.left?.left?.left = TreeNode(7)root.right?.right?.left = TreeNode(8)root.right?.right?.right = TreeNode(9)val result = deepestLeavesSumBFS(root)println("層數最深的葉子節點的和 (BFS): $result") // 應該輸出24
}

深度優先搜索（DFS）

// 定義二叉樹節點類
class TreeNode(var `val`: Int) {var left: TreeNode? = nullvar right: TreeNode? = null
}// DFS方法返回層數最深的葉子節點的和
fun deepestLeavesSumDFS(root: TreeNode?): Int {if (root == null) return 0var maxDepth = -1var sumAtMaxDepth = 0fun dfs(node: TreeNode?, depth: Int) {if (node == null) return// 如果是葉子節點if (node.left == null && node.right == null) {if (depth > maxDepth) {maxDepth = depthsumAtMaxDepth = node.`val`} else if (depth == maxDepth) {sumAtMaxDepth += node.`val`}} else {dfs(node.left, depth + 1)dfs(node.right, depth + 1)}}dfs(root, 0)return sumAtMaxDepth
}// 測試示例
fun main() {// 創建測試二叉樹//        1//       / \//      2   3//     / \   \//    4   5   6//   /       / \//  7       8   9val root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left?.left = TreeNode(4)root.left?.right = TreeNode(5)root.right?.right = TreeNode(6)root.left?.left?.left = TreeNode(7)root.right?.right?.left = TreeNode(8)root.right?.right?.right = TreeNode(9)val result = deepestLeavesSumDFS(root)println("層數最深的葉子節點的和 (DFS): $result") // 應該輸出24
}