[Swift]LeetCode653.两数之和IV-输入BST|TwoSumIV-InputisaBST

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

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

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

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

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

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

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

124ms

 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 findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
16         var list = [Int]()
17         inorder(root, &list)
18         
19         var i = 0
20         var j = list.count - 1
21         while i < j {
22             if list[i] + list[j] == k { return true }
23             if list[i] + list[j] < k { i += 1}
24             else { j -= 1}
25         }
26         
27         return false
28     }
29     
30     func inorder(_ root: TreeNode?, _ list: inout [Int]) {
31         guard let r = root else { return }
32         
33         inorder(r.left, &list)
34         list.append(r.val)
35         inorder(r.right, &list)
36     }
37 }

Runtime: 128 ms

Memory Usage: 20.2 MB

 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 findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
16         var set: Set<Int> = []
17         var result = false
18         func check(_ tree: TreeNode?) -> Bool {
19             if tree == nil {return false}
20             let val = tree!.val
21             if set.contains(k - val) {
22                 return true
23             }else {
24                 set.insert(val)
25                 return check(tree?.left) || check(tree?.right)
26             }
27         }
28         return check(root)
29     }
30 }

132ms

 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 findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
16         var dict = [Int: Int]()
17         return traverse(root, k , &dict)
18     }
19     
20     func traverse(_ root: TreeNode?, _ k: Int, _  dict: inout [Int: Int]) -> Bool {
21         guard let root = root else { return false }
22         let rem = k - root.val
23         if dict[rem] != nil {
24             return true
25         }
26         dict[root.val] = 1
27         return traverse(root.left, k, &dict) || traverse(root.right, k, &dict)
28     }
29 }

Runtime: 140 ms

Memory Usage: 20.2 MB

 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 findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
16         if root == nil {return false}
17         var st:Set<Int> = Set<Int>()
18         var q:[TreeNode?] = [root]
19         while (!q.isEmpty)
20         {
21             var t:TreeNode? = q.removeFirst()           
22             if st.contains(k - t!.val) {return true}
23             st.insert(t!.val)
24             if t?.left != nil {q.append(t!.left)}
25             if t?.right != nil {q.append(t!.right)}
26         }
27         return false
28     }
29 }

152ms

 1 class Solution {
 2   var arr : [Int] = []
 3     func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
 4         preOrder(root)
 5         var i = 0
 6         var j = arr.count - 1
 7         while i < j {
 8             let sum = arr[i] + arr[j]
 9             if sum == k {
10                 return true
11             } else if sum < k {
12                 i += 1
13             } else {
14                 j -= 1
15             }
16         }
17         return false
18     }
19     
20     func preOrder(_ root: TreeNode?) {
21         if root == nil {return}
22         preOrder(root?.left)
23         arr.append(root!.val)
24         preOrder(root?.right)
25     }
26 }

156ms

 1 class Solution {
 2     func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
 3         var dic = [Int:Int]()
 4         return find(root,k, &dic)
 5     }
 6     func find(_ root: TreeNode?, _ k: Int, _  dic: inout [Int:Int]) -> Bool {
 7         if let root = root {
 8             let value = k - root.val
 9             if dic[value] != nil {
10                 return true
11             }
12             dic[root.val] = root.val
13             return find(root.left,k,&dic) || find(root.right,k,&dic)
14         } else {
15             return false
16         }
17     }
18 }

164ms

 1 class Solution {
 2     
 3     var memo : Set<Int> = []
 4     var isSum = false
 5     
 6     func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
 7         guard let node = root else { return false }
 8         
 9         depthFS(node, k)
10         return isSum
11     }
12     
13     func depthFS(_ root: TreeNode?,_ k: Int){
14          
15         guard let node = root else { return }
16         
17         let complement = k - node.val
18         
19         if memo.contains(complement){
20             isSum = true
21         } else {
22             memo.insert(node.val)
23         }
24         
25         if let left = node.left{
26             findTarget(left, k)
27         }
28         
29         if let right = node.right{
30             findTarget(right, k)
31         }
32     }
33 }

172ms

 1 class Solution {
 2     func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
 3         if root == nil {
 4             return false
 5         }
 6         
 7         var nodeValueDict = [Int: Int]()
 8         var nodeArray = [TreeNode]()
 9         nodeArray.append(root!)
10         while nodeArray.count > 0 {
11             let frontNode = nodeArray[0]
12             let diff = k - frontNode.val
13             
14             if nodeValueDict[diff] != nil {
15                 return true
16             }
17             
18             nodeArray.removeFirst()
19             nodeValueDict[frontNode.val] = 1
20             
21             if frontNode.left != nil {
22                 nodeArray.append(frontNode.left!)
23             }
24             
25             if frontNode.right != nil {
26                 nodeArray.append(frontNode.right!)
27             }
28         }
29         
30         return false
31     }
32 }

196ms

 1 class Solution {
 2     func preorder(_ root: TreeNode?) -> [Int] {
 3         if let root: TreeNode = root {
 4             return preorder(root.left) + [root.val] + preorder(root.right)
 5         } else {
 6             return []
 7         }
 8     }
 9     
10     func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
11         var seenVals = Set<Int>()
12         
13         for val in preorder(root) {
14             if seenVals.contains(k - val) {
15                 return true
16             } else {
17                 seenVals.insert(val)
18             }
19         }
20         
21         return false
22     }
23 }

200ms

 1 class Solution {
 2     func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
 3         guard let root = root else{
 4             return false
 5         }
 6         var nSet = Set<Int>()
 7         var queue = [TreeNode]()
 8         queue.append(root)
 9             
10         while queue.count > 0{
11             let cur = queue.removeFirst()
12             nSet.insert(cur.val)
13             if let left = cur.left{
14                 queue.append(left)
15             }
16             if let right = cur.right{
17                 queue.append(right)
18             }
19         }
20         for n in Array(nSet){
21             if nSet.contains(k - n) && n != (k - n){
22                 return true
23             }
24         }
25         return false
26     }
27 }

220ms

 1 class Solution {
 2     
 3     var memo : Set<Int> = []
 4     // var isSum = false
 5     
 6     func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
 7         guard let node = root else { return false }
 8         
 9         return depthFS(node, k)
10     }
11     
12     func depthFS(_ root: TreeNode?,_ k: Int) -> Bool{
13          
14         guard let node = root else { return false}
15         
16         let complement = k - node.val
17         print(node.val)
18         if memo.contains(complement){
19             return true
20         } else {
21             memo.insert(node.val)
22         }
23         
24         return depthFS(node.left, k) || depthFS(node.right, k)
25     }
26 }