653. Two Sum IV - Input is a BST

Problem Statement

link: LeetCode.cn LeetCode Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Example:

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

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

Constraints: The number of nodes in the tree is in the range [1, 104]. -104 <= Node.val <= 104 root is guaranteed to be a valid binary search tree. -105 <= k <= 105

Solution Approach

1. DFS with Hash Set: Uses a set to store node values and performs a depth-first search to check if the complement of the current node’s value exists in the set.
2. BFS with Hash Set: Utilizes a breadth-first search approach with a queue to explore the tree level by level, checking for the complement of each node’s value in a set.
3. Inorder Traversal with Two Pointers: Converts the BST to a sorted array through inorder traversal, then applies the two-pointer technique to find if two numbers sum up to the target.
4. Two Pointers with Iterators: Implements two custom iterators to traverse the BST from both ends (smallest and largest values), using a two-pointer approach to find the target sum.

Algorithm

Implement

    class Solution: 
    def __init__(self):
        self.s = set()

    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        if root is None:
            return False
        if k - root.val in self.s:
            return True
        self.s.add(root.val)
        return self.findTarget(root.left, k) or self.findTarget(root.right, k)

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        s = set()
        q = deque([root])
        while q:
            node = q.popleft()
            if k - node.val in s:
                return True
            s.add(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return False
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        arr = []
        def inorderTraversal(node: Optional[TreeNode]) -> None:
            if node:
                inorderTraversal(node.left)
                arr.append(node.val)
                inorderTraversal(node.right)
        inorderTraversal(root)

        left, right = 0, len(arr) - 1
        while left < right:
            sum = arr[left] + arr[right]
            if sum == k:
                return True
            if sum < k:
                left += 1
            else:
                right -= 1
        return False

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        left, right = root, root
        leftStk, rightStk = [left], [right]
        while left.left:
            left = left.left
            leftStk.append(left)
        while right.right:
            right = right.right
            rightStk.append(right)
        while left != right:
            sum = left.val + right.val
            if sum == k:
                return True
            if sum < k:
                left = leftStk.pop()
                node = left.right
                while node:
                    leftStk.append(node)
                    node = node.left
            else:
                right = rightStk.pop()
                node = right.left
                while node:
                    rightStk.append(node)
                    node = node.right
        return False

    
    

Twitter  facebook  Email