python - inorder successor


  • 0
    S
    # 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 inorderSuccessor(self, root, p):
            """
            :type root: TreeNode
            :type p: TreeNode
            :rtype: TreeNode
            """
            if not p:
                return None
            
            # keep path for later use
            curr, stack = root, []
            while curr and curr != p:
                stack.append(curr)
                curr = curr.left if p.val < curr.val else curr.right
            
            if not curr:
                return None
            
            # if p has a right child,
            # the successor exists in the right subtree
            succ = curr.right
            while succ and succ.left:
                succ = succ.left
            
            if succ:
                return succ
            
            # use the path and find the first 
            # ancestor p greater than p
            # such ancestor is the successor in 
            # the inorder traversal
            while stack:
                parent = stack.pop()
                if p.val < parent.val:
                    return parent
            
            return None
    

Log in to reply
 

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