129. Sum Root to Leaf Numbers

129. Sum Root to Leaf Numbers

题目描述

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

1
2
3
4
5
6
7
8
9
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

题目大意

根节点到子节点的路径代表一个数,求所有路径的数值的和。

1
2
3
4
5
6
7
1
/ \
2 3
根节点到子节点的路径 1->2 代表数值:12
根节点到子节点的路径 1->3 代表数值:13
返回结果 25

解题思路

DFS(深度优先搜索)
遍历左右子树,直到左右子树都为nil。则代表这一路径的数值已经组合完毕。

代码

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func sumNumbers(_ root: TreeNode?) -> Int {
var ans = 0
func dfs(tree: TreeNode?, pre: Int) -> Int {
guard let t = tree else { return 0 }
let n = pre * 10 + t.val
if t.left == nil && t.right == nil {
return n
}
return dfs(tree: t.left, pre: n) + dfs(tree: t.right, pre: n)
}
return dfs(tree: root, pre: 0)
}
}
0%