[Swift]LeetCode113.路径总和II|PathSumII

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

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

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

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

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

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

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

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

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

[
   [5,4,11,2],
   [5,8,4,5]
]

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 pathSum(_ root: TreeNode?, _ sum: Int) -> [[Int]] {
16         var resArray =  [[Int]]()
17         if root == nil {
18             return resArray
19         }
20 
21         if root?.left == nil && root?.right == nil {
22             if root!.val == sum {
23                 let nodeArray = [Int](repeating:root!.val,count:1)
24                 resArray.append(nodeArray)
25             }
26             return resArray
27         }
28 
29         var nodeArray =  [Int]()
30         helper(root,sum,&resArray,&nodeArray)
31         return resArray
32     }
33 
34     func helper(_ root: TreeNode?, _ sum: Int, _ array: inout [[Int]], _ nodeArray: inout [Int]) {
35         if root == nil {
36             return
37         }
38 
39         if root?.left == nil && root?.right == nil {
40             if sum-root!.val == 0 {
41                 nodeArray.append(root!.val)
42                 array.append(nodeArray)
43                 nodeArray.remove(at:nodeArray.count-1)
44             }
45             return
46         }
47         
48         nodeArray.append(root!.val)
49         helper(root?.left,sum-root!.val,&array,&nodeArray) 
50         helper(root?.right,sum-root!.val,&array,&nodeArray)
51         let index = nodeArray.count - 1
52         nodeArray.remove(at:index)
53     }
54 }

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 pathSum(_ root: TreeNode?, _ sum: Int) -> [[Int]] {
16         var ans = [[Int]]()
17         var combination = [Int]()
18         pathSum(root, sum, &combination, &ans)
19         return ans
20     }
21     
22     func pathSum(_ node: TreeNode?, _ sum: Int, _ combination: inout [Int], _ ans: inout [[Int]]) {
23         guard let node = node else { return }
24         
25         combination.append(node.val)
26         
27         if node.left == nil && node.right == nil && (sum - node.val) == 0 {
28             ans.append(combination)
29         }     
30         
31         pathSum(node.left, sum - node.val, &combination, &ans)
32         pathSum(node.right, sum - node.val, &combination, &ans)
33         
34         combination.removeLast()
35     }
36 }

32ms

 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 pathSum(_ root: TreeNode?, _ sum: Int) -> [[Int]] {
16         if root == nil { return []}
17         var result = [[Int]]()
18         var currentRun = [Int]()
19         checkSum(root, sum, &result, &currentRun)
20         return result
21         
22     }
23     func checkSum(_ root: TreeNode?, _ sum: Int,_ result: inout [[Int]],_ currentRun: inout [Int] ) {
24         if root == nil { return }
25         var current = currentRun
26         current.append(root!.val)
27         if sum - root!.val == 0 && root!.left == nil && root!.right == nil {
28             result.append(current)
29             return
30         }
31         checkSum(root!.left, sum - root!.val, &result, &current)
32         checkSum(root!.right, sum - root!.val, &result, &current)
33     }
34 }

52ms

 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 pathSum(_ root: TreeNode?, _ sum: Int) -> [[Int]] {
16         var paths: [[Int]] = []
17         BFS(root, sum: sum, paths: &paths)
18         return paths
19     }
20     
21     func BFS(_ root: TreeNode?, sum: Int, paths: inout [[Int]], path: [Int]? = nil) {
22         guard let root = root else { return }
23         var path: [Int] = path ?? []
24         path.append(root.val)
25         if root.left == nil && root.right == nil {
26             if sum == path.reduce(0) { $0 + $1 } {
27                 paths.append(path)
28             }
29             return
30         }
31         BFS(root.left, sum: sum, paths: &paths, path: path)
32         BFS(root.right, sum: sum, paths: &paths, path: path)
33     }
34 }

56ms

 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 pathSum(_ root: TreeNode?, _ sum: Int) -> [[Int]] {
16         guard let root = root else {
17             return []
18         }
19     
20         if root.left == nil && root.right == nil && root.val == sum {
21             return [[sum]]
22         }
23     
24         let lPathSum = pathSum(root.left, sum - root.val)
25         let rPathSum = pathSum(root.right, sum - root.val)
26     
27         return (lPathSum + rPathSum).map {
28             [root.val] + $0
29         }
30     }
31 }