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

案例 1:

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

Target = 9

输出: True

案例 2:

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

Target = 28

输出: False

Solution

• 对BST中序遍历得到中序数组后，得到有序数组，在利用双指针来判断

解法同：[167 两数之和 II](167 两数之和 II.md)

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        numbers = []
        def inOrder(root):
            if not root:
                return
            inOrder(root.left)
            numbers.append(root.val)
            inOrder(root.right)
        
        inOrder(root)        
        left, right = 0, len(numbers)-1
        while left<right:
            sumLR = numbers[left]+numbers[right]
            if sumLR==k:
                return True
            elif sumLR<k:
                left+=1
            elif sumLR>k:
                right-=1
        return False
        
# @lc code=end

• 利用 set 和dfs

参考思路：jue-qiang-zha-zha

class Solution(object):
    def findTarget(self, root, k):
        num = set()
        def find(root, k):
            if not root:
                return False
            if k-root.val in num:
                return True
            num.add(root.val)
            return find(root.left, k) or find(root.right, k)
        
        return find(root, k)