Python solution making use of the BST property


  • 0
    H
    class Solution(object):
        def findTarget(self, root, k):
            # Without caring that it's a BST
            """
            our_set = set()
            def find_it(root, k):
                if root:
                    target = k - root.val
                    if target in our_set:            
                        return True
                    our_set.add(root.val)
                    return find_it(root.left, k) or find_it(root.right, k)
                return False
            return find_it(root, k)
            """
            
            # BST solution
            # BST -> inorder transveral results in sorted list
            # Looking for a sum of two numbers in a sorted list is easy with two pointers
            l = []
            def inorder(root):
                if root:
                    inorder(root.left)
                    l.append(root.val)
                    inorder(root.right)            
            inorder(root)
            low = 0
            high = len(l) - 1
            while low < high:
                sum_ = l[low] + l[high]
                if sum_ == k:
                    return True
                elif sum_ < k:
                    low += 1
                else:
                    high -= 1
            return False
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.