leetcode链接:https://leetcode-cn.com/problems/deepest-leaves-sum/
题目描述:
给你一棵二叉树的根节点 root ,请你返回 层数最深的叶子节点的和 。
思路1: 两次递归
最直接的思路是 1: 先得到树的最大深度;2: 将最大深度的节点值相加。这样需要两次递归。
func deepestLeavesSum(root *TreeNode) int {
//最大深度
depth := deepestDepth(root)
//最大深度叶子结点
nums := []int{}
findDeepest(root, &nums, depth)
//相加求和
var result int
for _, n := range nums {
result += n
}
return result
}
//获取最大深度的叶子结点
func findDeepest(root *TreeNode, nums *[]int, depth int) {
if root == nil {
return
}
if depth == 1 {
if root != nil {
*nums = append(*nums, root.Val)
}
}
findDeepest(root.Left, nums, depth - 1)
findDeepest(root.Right, nums, depth - 1)
}
//获取最大深度
func deepestDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil && root.Right == nil {
return 1
}
depthLeft := deepestDepth(root.Left)
depthRight := deepestDepth(root.Right)
if depthLeft > depthRight {
return depthLeft + 1
} else {
return depthRight + 1
}
}
思路2: 层序遍历
通过层序遍历的方式获取每一层叶子结点,计算最后一层结点的和。这个思路会有额外的空间浪费。
func deepestLeavesSum(root *TreeNode) int {
//取出最后一层叶子结点加和
result := levelTree(root)
sum := 0
if len(result) > 0 {
for _, n := range result {
sum += n
}
}
return sum
}
//层序遍历,取出最后一层叶子结点
func levelTree(root *TreeNode) []int {
var result [][]int
if root == nil {
return nil
}
level := []*TreeNode{root}
for len(level) > 0 {
var levelLeaves []int
levelTemp := []*TreeNode{}
for i := 0; i < len(level); i ++ {
levelLeaves = append(levelLeaves, level[i].Val)
if level[i].Left != nil {
levelTemp = append(levelTemp, level[i].Left)
}
if level[i].Right != nil {
levelTemp = append(levelTemp, level[i].Right)
}
}
level = levelTemp
result = append(result, levelLeaves)
}
if len(result) > 0 {
return result[len(result) - 1]
}
return []int{}
}
思路3: 最优解 维护两个变量
递归求树的最大深度,同时维护两个全局变量 maxdep 和 sum,其中 maxdep表示搜索到的节点的最大深度,sum表示搜索到的深度等于 maxdep 的节点的权值之和。
// sum为最终的和, maxdep为树的最大深度
var sum, maxdep int
func deepestLeavesSum(root *TreeNode) int {
sum, maxdep = 0, 0
deepestDepth(root, 0)
return sum
}
func deepestDepth(root *TreeNode, depth int) {
if root == nil {
return
}
if depth > maxdep {
maxdep = depth
sum = root.Val
} else if depth == maxdep {
sum += root.Val
}
deepestDepth(root.Left, depth + 1)
deepestDepth(root.Right, depth + 1)
}