文章目录
  1. 1. 首先定义二叉树
  2. 2. DFS解法

离职后在家里投简历,然后碰巧看到一个群里在讨论算法,又加上想写Swift了,于是闲来无事顺手做了一下

题目地址:129. Sum Root to Leaf Numbers

看到题目第一反应就是 DFS 呀,遍历找到所有的数字,然后加起来就可以了。

首先定义二叉树

1
2
3
4
5
6
7
8
9
10
11
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
}
}

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
class Solution {
func sumNumbers(_ root: TreeNode?) -> Int {

totalSum = 0
sum1(root: root)
return totalSum
}


var totalSum = 0
var s = 0

func sum1(root: TreeNode?)
{
if root == nil {return}

s = s*10 + root!.val
if root!.left == nil && root!.right == nil
{
totalSum += s
}
else
{
sum1(root: root!.left)
sum1(root: root!.right)
}
s /= 10
}
}
}

这种解法比较麻烦,后来参考了一下其他人的写法发现一行代码就能搞定,方法如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
func sumNumbers(_ root: TreeNode?) -> Int {

return sum(root: root, s: 0)
}

func sum(root: TreeNode?, s: Int) -> Int
{
return root == nil ? 0 : (root!.left == nil && root!.right == nil) ? root!.val + s * 10 : sum(root: root!.left, s: root!.val + s * 10) + sum(root: root!.right, s: root!.val + s * 10)
}
}

很久没有写算法了,加上Swift的语法也改变了,这次踩了很多坑,也捡起来了很多东西。

文章目录
  1. 1. 首先定义二叉树
  2. 2. DFS解法