653. Two Sum IV - Input is a BST

Difficulty: Easy

link: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

1. Sorted Array + Two Pointer

$O(n)$ runtime, $O(n)$ space

最直觀想到的作法，先 inorder 跑一遍 BST，將元素依小至大的順序存進一個 list，那這個問題就被化簡為 Two Sum II - Input array is sorted，再搭配 two pointer 的作法，時間和空間複雜度都會是$O(n)$。

python

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        self.sorted_array = []
        self.inorder(root)
        
        i, j = 0, len(self.sorted_array)-1
        while i < j:
            two_sum = self.sorted_array[i] + self.sorted_array[j]
            if two_sum == k:
                return True
            elif two_sum > k:
                j -= 1
            else:
                i += 1
        
        return False
        
    def inorder(self, node):
        if node is None:
            return
        self.inorder(node.left)
        self.sorted_array.append(node.val)
        self.inorder(node.right)

Accepted
Runtime: 92 ms, faster than 34.56% of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: 19.3 MB, less than 28.76% of Python3 online submissions for Two Sum IV - Input is a BST.

2. Hash Table

$O(n)$ runtime, $O(n)$ or $O(logn)$ space

在前一題 Two Sum II - Input array is sorted 的 two pointer 作法優點是 $O(1)$ 的空間複雜度，然而這題化簡用的 list 卻需要 $O(n)$ 的空間複雜度，那其實也能用 Two Sum 的 hash table 作法，一旦找到答案就 return，會比前一個作法全部都找一遍還快些。

這裡用 BFS 來 traverse BST。另外，如果題目有保證 BST 是 balanced，那麼 DFS 的做法可以到 $O(logn)$ 空間複雜度，因為 stack 裡面最多存放 BST height 個 node。

python

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        queue, hashtable = [root], set()
        while queue:
            node = queue.pop()
            if k - node.val in hashtable: 
                return True
            hashtable.add(node.val)
            if node.left: 
                queue.append(node.left)
            if node.right: 
                queue.append(node.right)
                
        return False

Accepted
Runtime: 80 ms, faster than 67.18% of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: 16.6 MB, less than 71.99% of Python3 online submissions for Two Sum IV - Input is a BST.

tags: leetcode