[Swift]LeetCode129.求根到叶子节点数字之和|SumRoottoLeafNumbers

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

示例 2:

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

12ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func sumNumbers(_ root: TreeNode?) -> Int {
16         guard let root = root else { return 0 }
17         var sum = 0
18         var stack: [(node: TreeNode, accum: Int)] = [(node: root, accum: 0)]
19         
20         while !stack.isEmpty {
21             let currentVal = stack.removeLast()
22             let updatedAccum = currentVal.accum * 10 + currentVal.node.val
23             
24             guard currentVal.node.left != nil || currentVal.node.right != nil else {
25                 sum += updatedAccum
26                 continue
27             }
28             
29             if let leftNode = currentVal.node.left {
30                 stack.append((node: leftNode, accum: updatedAccum))
31             }
32             
33             if let rightNode = currentVal.node.right {
34                 stack.append((node: rightNode, accum: updatedAccum))
35             }
36         }
37         
38         return sum
39     }
40     
41 }

16ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func sumNumbers(_ root: TreeNode?) -> Int {
16         if root == nil { return 0 }
17         else {
18             let result = getNumber(root!, 0)
19             return result
20         }
21     }
22     
23     func getNumber(_ node: TreeNode, _ number: Int) -> Int {
24         let currentNumber = number * 10 + node.val
25         var result = 0
26         if node.left == nil && node.right == nil {
27             return currentNumber
28         } else if node.left == nil {
29             result = getNumber(node.right!, currentNumber)
30         } else if node.right == nil {
31             result = getNumber(node.left!, currentNumber)
32         } else {
33             result = getNumber(node.left!, currentNumber) + getNumber(node.right!, currentNumber)
34         }
35         return result
36     }
37 }

20ms

 1 class Solution {
 2     func sumNumbers(_ root: TreeNode?) -> Int {
 3         let nums = numbers(root)
 4         print(nums)
 5         return nums.reduce(0, { $0 + Int($1)! })
 6     }
 7     
 8     func numbers(_ root: TreeNode?) -> [String] {
 9         guard let root = root else { return [] }
10         
11         if root.left == nil && root.right == nil {
12             return [String(root.val)]
13         }
14         
15         return (numbers(root.left) + numbers(root.right)).map { String(root.val) + $0 }
16     }
17 }

24ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func sumNumbers(_ root: TreeNode?) -> Int {
16             var sum = 0
17             treeShowNodeVal(root: root, item: "", sum: &sum)
18             return sum
19         }
20         func treeShowNodeVal(root: TreeNode?, item: String, sum: inout Int){
21             if root == nil {
22                 return
23             }
24             var newItem = item
25             newItem.append(String((root?.val)!))
26             if root?.left == nil && root?.right == nil {
27                 let itemValue = Int(newItem)
28                 sum = sum + itemValue!
29             }
30             treeShowNodeVal(root: root?.left, item: newItem, sum: &sum)
31             treeShowNodeVal(root: root?.right, item: newItem, sum: &sum)
32         }
33 }

28ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func sumNumbers(_ root: TreeNode?) -> Int {
16         var array = [String]()
17         guard let root = root else { return 0 }
18         
19         func helper(_ node: TreeNode, _ temp: String) {
20             var temp = temp + "\(node.val)"
21             if node.left == nil && node.right == nil {
22                 array.append(temp)
23             } else {
24                 if let left = node.left {
25                     helper(left, temp)    
26                 }
27                 if let right = node.right {
28                     helper(right, temp)    
29                 }
30             }
31         }
32         
33         helper(root, "")
34         return array.reduce(0, {return $0 + Int($1)!})
35     }
36 }