129. 求根节点到叶节点数字之和

题目描述

给你一个二叉树的根节点 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

解法一：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    if root == nil {
        return 0
    }
    sum := 0
    var dfs func(root *TreeNode, num int)
    dfs = func(root *TreeNode, num int) {
        num = num*10 + root.Val
        if root.Left == nil && root.Right == nil {
            sum += num
            return
        }
        if root.Left != nil {
            dfs(root.Left, num)
        }
        if root.Right != nil {
            dfs(root.Right, num)
        }
    }
    dfs(root, 0)
    return sum
}

解法二：BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    sum := 0
    if root == nil {
        return sum
    }
    type qElem struct {
        node *TreeNode
        num  int
    }
    var queue []qElem
    queue = append(queue, qElem{root, root.Val})
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        if cur.node.Left == nil && cur.node.Right == nil {
            sum += cur.num
        }
        if cur.node.Left != nil {
            queue = append(queue, qElem{cur.node.Left, cur.num*10 + cur.node.Left.Val})
        }
        if cur.node.Right != nil {
            queue = append(queue, qElem{cur.node.Right, cur.num*10 + cur.node.Right.Val})
        }
    }
    return sum
}