Inorder Successor

https://leetcode.com/problems/inorder-successor-in-bst-ii/

这道题求解下一个比当前node值大的node，只有两种情况。

1. 第一个比当前node大的parent （具体画画就知道了）当前node在向上找parent时很可能一直在parent的右子树里面，找到第一个它在左子树里的parent就是我们要找的parent

2. 当前node的right subtree里面最小的那个node

class Solution(object):
    def inorderSuccessor(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        v = node.val
        if node.right:
            node = node.right
            while node.left:
                node = node.left
            return node
        
        
        while node.parent and node.val <= v:
            node = node.parent
        if node.val <= v:
            return None
        return node

这是在有parent的情况下。如果没有parent就如如下情况。

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        if p.right:
            node = p.right
            while node.left:
                node = node.left
            return node
        res = None
        while root:
            if root.val > p.val:
                res = root
                root = root.left
            else:
                root = root.right
        return res

这里我们每找到一个root root.val > p.val 我们都assume这是我们找到的最后一个比p大的父并用res记录它

另一个解法，leftMost解法 + prev

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        if p.right:
            p = p.right
            while p.left:
                p = p.left
            return p
        stack = []
        prev = float("-inf")
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if prev == p.val:
                return root
            prev = root.val
            root = root.right
        return None