two pointers on BST, O(n) time, O(lgn) average space


  • 1
    A
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def findTarget(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: bool
            """
            # # using hash set
            # vals = set()
            # def inorder(node):
            #     if node:
            #         if inorder(node.left):
            #             return True
            #         if k - node.val in vals:
            #             return True
            #         vals.add(node.val)
            #         if inorder(node.right):
            #             return True
            #     return False
            # return inorder(root)
            
            # two pointer
            stack_forward = []
            stack_backward = []
            p = root
            while p:
                stack_forward.append(p)
                p = p.left
            p = root
            while p:
                stack_backward.append(p)
                p = p.right
            while stack_forward and stack_backward:
                if stack_forward[-1].val == stack_backward[-1].val:
                    break
                if stack_forward[-1].val + stack_backward[-1].val == k:
                    return True
                if stack_forward[-1].val + stack_backward[-1].val < k:
                    p = stack_forward.pop().right
                    while p:
                        stack_forward.append(p)
                        p = p.left
                else:
                    p = stack_backward.pop().left
                    while p:
                        stack_backward.append(p)
                        p = p.right
            return False
                
    

  • 0

    Just wanted to see how it would look when I separate the three parts (forward iteration, backward iteration, and main algorithm)...

    def findTarget(self, root, k):
    
        def forward(root):
            stack = []
            p = root
            while p:
                stack.append(p)
                p = p.left
            while stack:
                yield stack[-1].val
                p = stack.pop().right
                while p:
                    stack.append(p)
                    p = p.left
            yield None
            
        def backward(root):
            stack = []
            p = root
            while p:
                stack.append(p)
                p = p.right
            while stack:
                yield stack[-1].val
                p = stack.pop().left
                while p:
                    stack.append(p)
                    p = p.right
            yield None
    
        forward = forward(root)
        backward = backward(root)
        f, b = next(forward), next(backward)
        while f is not None is not b:
            if f == b:
                break
            if f + b == k:
                return True
            if f + b < k:
                f = next(forward)
            else:
                b = next(backward)
        return False

  • 0

    And another version...

    def findTarget(self, root, k):
        
        def vals(root, forward=True):
            stack = []
            p = root
            while p or stack:
                while p:
                    stack.append(p)
                    p = p.left if forward else p.right
                p = stack.pop()
                yield p.val
                p = p.right if forward else p.left
            yield None
    
        forward = vals(root)
        backward = vals(root, forward=False)
        f, b = next(forward), next(backward)
        while f != b:
            if f + b == k:
                return True
            if f + b < k:
                f = next(forward)
            else:
                b = next(backward)
        return False

Log in to reply
 

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