[LeetCode] Challenge log 653

Posted on |
653. Two Sum IV - Input is a BST

solution 1: use set.

solution 2: use the fact that a sorting array is given.

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.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        def inorder(root, arr):
            if root is None:
                pass
            else:
                inorder(root.left, arr)
                arr.append(root.val)
                inorder(root.right, arr)
                
        arr = []
        inorder(root, arr)
        count = set()
        for i in arr:
            if k-i not in count:
                count.add(i)
            else:
                return True
        return False
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
26
27
class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        def inorder(root, arr):
            if root is None:
                pass
            else:
                inorder(root.left, arr)
                arr.append(root.val)
                inorder(root.right, arr)
                
        arr = []
        inorder(root, arr)
        l = 0
        r = len(arr) - 1
        while l < r:
            if arr[l] + arr[r] == k:
                return True
            elif arr[l] + arr[r] < k:
                l += 1
            else:
                r -= 1
        return False
0%