653. 两数之和 IV - 输入 Easy BST 85.00

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

案例 1:

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

Target = 9

输出: True
 

案例 2:

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

Target = 28

输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

结果

执行用时：164 ms, 在所有 Swift 提交中击败了85.00%的用户
内存消耗：15.3 MB, 在所有 Swift 提交中击败了37.50%的用户

思路

第一次，用数组存储node，以[Int: Int]字典存储val，遍历二叉树，速度只超过65%
第二次，看完官方题解1，改成递归遍历（递归并没有节省多少时间），以Set<Int>存储value，速度超过85%
另外两种题解还没有尝试

代码

class Solution {
    var numSet: Set<Int> = []
    func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
      return findTargetInChildNode(root, k)
    }

    func findTargetInChildNode(_ root: TreeNode?, _ k: Int) -> Bool {
        guard let root = root else { return false } 
        if numSet.contains(k - root.val) {
            return true
        }
        numSet.insert(root.val)
        return findTargetInChildNode(root.left, k) || findTargetInChildNode(root.right, k)
    }
}