Python, traverse while keeping a window with size 2


  • 0
    O

    Just use the inorder traverse and keep a window/register with size 2, which keep track of two nodes just traversed.

    The only critical part is where to check the window and stop traverse.

    But after you figure it out, it's quite straightforward I guess

    def inorderSuccessor(self, root, p):
        window = [None]*2
        self.inorderHelper(root, p, window)
        return window[-1] if window[-1] != p else None
        
    def inorderHelper(self, node, p, window):
        if node.left:
            self.inorderHelper(node.left, p, window)
        if window[0] == p and window[1]: #already find the successor!
            return
        elif window[0] and window[1]: #update the window
            window[0], window[1] = window[1], node
        elif window[0] and not window[1]: #node is successor of root
            window[1] = node
        else: #node is root
            window[0] = node
        if node.right:
            self.inorderHelper(node.right, p, window)

Log in to reply
 

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