# 653. Two Sum IV - Input is a BST

{% embed url="<https://leetcode.com/problems/two-sum-iv-input-is-a-bst/>" %}

### BST性质解法：

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

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

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

{% content-ref url="94.-binary-tree-inorder-traversal" %}
[94.-binary-tree-inorder-traversal](https://xuqiangwen1994.gitbook.io/practice/94.-binary-tree-inorder-traversal)
{% endcontent-ref %}

{% content-ref url="167.-two-sum-ii-input-array-is-sorted" %}
[167.-two-sum-ii-input-array-is-sorted](https://xuqiangwen1994.gitbook.io/practice/167.-two-sum-ii-input-array-is-sorted)
{% endcontent-ref %}

```python
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性质解的。

```python
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
```
