Two Sum IV - Input is a BST

Intuition

We could get sorted list of the BST's values by inorder traversal. And then, solve it using the same way of two sum problem in sorted list.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findTarget(self, root: TreeNode, target: int) -> bool:
        inorder = []
        self._inorder(root, inorder)
        i = 0
        j = len(inorder) - 1
        while i < j:
            tmp = inorder[i] + inorder[j]
            if tmp == target:
                return True
            elif tmp < target:
                i += 1
            else:
                j -= 1
        return False

    def _inorder(self, node, inorder):
        if node is None:
            return
        self._inorder(node.left, inorder)
        inorder.append(node.val)
        self._inorder(node.right, inorder)