★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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 7Target = 9Output: True
Example 2:
Input: 5 / \ 3 6 / \ \2 4 7Target = 28Output: False
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入: 5 / \ 3 6 / \ \2 4 7Target = 9输出: True
案例 2:
输入: 5 / \ 3 6 / \ \2 4 7Target = 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 = nil10 * self.right = nil11 * }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 = 020 var j = list.count - 121 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 false28 }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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {16 var set: Set = []17 var result = false18 func check(_ tree: TreeNode?) -> Bool {19 if tree == nil { return false}20 let val = tree!.val21 if set.contains(k - val) {22 return true23 }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 = nil10 * self.right = nil11 * }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.val23 if dict[rem] != nil {24 return true25 }26 dict[root.val] = 127 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 = nil10 * self.right = nil11 * }12 * }13 */14 class Solution {15 func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {16 if root == nil { return false}17 var st:Set = Set ()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 false28 }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 true11 } else if sum < k {12 i += 113 } else {14 j -= 115 }16 }17 return false18 }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 true11 }12 dic[root.val] = root.val13 return find(root.left,k,&dic) || find(root.right,k,&dic)14 } else {15 return false16 }17 }18 } 164ms
1 class Solution { 2 3 var memo : Set = [] 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 isSum11 }12 13 func depthFS(_ root: TreeNode?,_ k: Int){14 15 guard let node = root else { return }16 17 let complement = k - node.val18 19 if memo.contains(complement){20 isSum = true21 } 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.val13 14 if nodeValueDict[diff] != nil {15 return true16 }17 18 nodeArray.removeFirst()19 nodeValueDict[frontNode.val] = 120 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 false31 }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 ()12 13 for val in preorder(root) {14 if seenVals.contains(k - val) {15 return true16 } else {17 seenVals.insert(val)18 }19 }20 21 return false22 }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 () 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 true23 }24 }25 return false26 }27 } 220ms
1 class Solution { 2 3 var memo : Set = [] 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.val17 print(node.val)18 if memo.contains(complement){19 return true20 } else {21 memo.insert(node.val)22 }23 24 return depthFS(node.left, k) || depthFS(node.right, k)25 }26 }