给定一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1:输入:root = [1,2,3] 输出:25
解释:从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25
示例 2:输入:root = [4,9,0,5,1] 输出:1026
解释:从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026
提示:树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10
注意:本题与主站 129 题相同:
1、递归;时间复杂度O(n),空间复杂度O(log(n))
var res int
func sumNumbers(root *TreeNode) int {
res = 0
dfs(root, 0)
return res
}
func dfs(root *TreeNode, sum int) {
if root == nil {
return
}
sum = sum*10 + root.Val
if root.Left == nil && root.Right == nil {
res = res + sum
}
dfs(root.Left, sum)
dfs(root.Right, sum)
}
2、迭代;时间复杂度O(n),空间复杂度O(n)
func sumNumbers(root *TreeNode) int {
res := 0
if root == nil {
return res
}
list := make([]*TreeNode, 0)
list = append(list, root)
for len(list) > 0 {
length := len(list)
for i := 0; i < length; i++ {
node := list[i]
value := node.Val
if node.Left == nil && node.Right == nil {
res = res + value
}
if node.Left != nil {
node.Left.Val = node.Left.Val + value*10
list = append(list, node.Left)
}
if node.Right != nil {
node.Right.Val = node.Right.Val + value*10
list = append(list, node.Right)
}
}
list = list[length:]
}
return res
}
Medium题目,题目同leetcode 129.求根到叶子节点数字之和
页面更新:2024-03-21
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号