Python Intuitive Two Approaches

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

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