Two Sum IV - Input is a BST

Posted on | Edited on | In | | Views:

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

这是经典题Two Sum的变形, 于经典题不同的是, 这个输入从数组, 换成了二叉搜索树. 但是, 我们还是可以按照经典题的做法取解这道题.

思路

由于这道题的输入是一个二叉搜索树, 所以我们可以利用二叉搜索树的一些特点来帮助我们解决这道题. 大家都知道二叉搜索树的最重要的特点, 就是左子树永远比根节点小, 右子树永远比根节点要大. 那么利用这个特点, 中序遍历二叉搜索树, 我们就可以得到一个升序的数组. 这就可以用双指针的方法来做了.

  1. 定义一个左指针, 指向0. 一个右指针, 指向末尾
  2. 当左指针和右指针的和等于target的时候, 返回true
  3. 当左指针和右指针的和小于target的时候, 我们要把左指针往右挪一位
  4. 相反的, 我们要把右指针往左挪一位
  5. 当右指针小于等于左指针的时候, 返回false

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def inorder(root):
    res = list()
    if not root:
        return res
    
    res += self.inorder(root.left)
    res += [root.val]
    res += self.inorder(root.right)

    return res

def twoSum(root, target):
    if not root:
        return False
    res = inorder(root)
    left = 0
    right = len(root)-1
    while left < right:
        if res[left] + res[right] == target:
            return True
        if res[left] + res[right] < k:
            left += 1
        else:
            right -= 1
    return False

复杂度

$O(n)$, 因为我们需要遍历这个数, $n$是这棵树的节点数

EOF