653. Two Sum IV – Input is a BST-两数之和 IV – 输入 BST

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

Example 1:
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Example 3:
Input: root = [2,1,3], k = 4
Output: true

Example 4:
Input: root = [2,1,3], k = 1
Output: false

Example 5:
Input: root = [2,1,3], k = 3
Output: true

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^4 <= Node.val <= 10^4
• root is guaranteed to be a valid binary search tree.
• -10^5 <= k <= 10^5

Solution in python:

# 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:
        alist = []
        def traverse(root):
            if root == None:
                return 
            else:
                traverse(root.left)
                nonlocal alist
                alist.append(root.val)
                traverse(root.right)
        traverse(root)
        i = 0
        j = len(alist)-1
        while i < j:
            if alist[i]+alist[j] > k:
                j -= 1
            elif alist[i]+alist[j] < k:
                i += 1
            else:
                return True
        return False