Python Intuitive Two Approaches


  • 0
    D

    a) inorder traverse tree, and use set to record value visited before. But this approach is not related to BST particularly, it works on any binary tree. Run time 129 ms.

    class Solution(object):
        def findTarget(self, root, k):
            visited = set()
            return self.dfs(root, k, visited)
    
        def dfs(self, root, target, visited):
            if not root:
                return False
            if self.dfs(root.left, target, visited):
                return True
            if target - root.val in visited:
                return True
            visited.add(root.val)
            if self.dfs(root.right, target, visited):
                return True
            return False
    

    b) Similar to original two sums. As BST is sorted in ascending order, then we can keep track of low & high values. Run time 175 ms.

    class Solution(object):
        def findTarget(self, root, k):
            if not root:
                return False
            low_iter, high_iter = TreeIterator(root, True), TreeIterator(root, False)
            low, high = low_iter.next(), high_iter.next()
            while low < high:
                if low + high > k:
                    high = high_iter.next()
                elif low + high < k:
                    low = low_iter.next()
                else:
                    return True
            return False
    
    class TreeIterator(object):
        def __init__(self, root, is_incr):
            self.stack = [root]
            self.is_incr = is_incr
            self.push_stack(root)
        
        def next(self):
            node = self.stack.pop()
            self.push_stack(node.right if self.is_incr else node.left)
            return node.val
    
        def push_stack(self, node):
            while node:
                self.stack.append(node)
                node = node.left if self.is_incr else node.right
    

Log in to reply
 

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