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%