Inorder predecessor and successor

题目描述

对于inorder traversal两个概念

• predecessor
• successor

解题方法

search for key

首先是search for that key

• if key < node.val, goto left subtree and set successor as node
• if key > node.val, goto right subtree and set predecessor as node
• find key

predecessor

if key is found

• if left subtree is not None, the predecessor is the right most child of leftsubtree
• else, predecessor is predecessor or None

successor

if key is found

• if right subtree is not None, the successor is the left most child of right subtree
• else, successor is last successor or None

Solution

successor

class Solution(object):
    def __init__(self):
        self.successor = None

    def inorderSuccessor(self, root, p):
        def leftmost(root):
            while root.left:
                root = root.left
            return root
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return

        if root.val == p.val:
            if root.right:
                tmp = leftmost(root.right) # find leftmost
                self.successor = tmp
            return self.successor
        elif root.val < p.val:
            return self.inorderSuccessor(root.right, p)
        else:
            self.succesor = root
            successor = self.inorderSuccessor(root.left, p)
            if successor:
                return successor
            else:
                return root

Reference

• predecessor and successor