653. Two Sum IV - Input is a BST

Loading...LeetCode

BST性质解法：

做了Q167的话这题还是很顺的，Q167是sorted array确认two sum，这边只是改成了BST，而利用BST这个性质可以在O(N)得到sorted array，最后总时间还是可以控制在O(N)：

BST 的 inorder traversal 是一个有序递增数组

所以也就是Q167起初上多做一个inorder traversal，做法见Q94：

94. Binary Tree Inorder Traversal167. Two Sum II - Input array is sorted

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        inorder, stack = [], []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            inorder.append(cur.val)
            cur = cur.right
        
        l, r = 0, len(inorder)-1
        while l < r:
            _sum = inorder[l] + inorder[r]
            if _sum == k: return True
            elif _sum < k: l += 1
            else: r -= 1
        return False

Hash set 解法：

也可以不去管BST性质，直接设置一个hash set来记录走过的点，然后遍历tree，看当前节点的值是否能与hash set 中任何值组成k。这个解法比较 general 且好懂，而且就这道题来看，其实平均时间/空间复杂度上都应该是优于利用BST性质解的。

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        memo = set()
        q = collections.deque([root])
        while q:
            cur = q.popleft()
            if k - cur.val in memo: return True
            memo.add(cur.val)
            if cur.left: q.append(cur.left)
            if cur.right: q.append(cur.right)
        return False