Inorder Successor

这个也算是BST的基本操作了，最优解必然得是O(h)的，解法也很简单，设置一个suc节点，每次搜索目标节点时会判断往左还是往右，如果是往左，则更新suc为当前点，往右不管，最后返回suc就行，下面是代码

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        suc = None
        cur = root
        while cur:
            if cur.val > p.val:
                suc = cur
                cur = cur.left
            else:
                cur = cur.right

        return suc

延伸：其实这个代码就已经能看出所有二叉树的inorder successor是怎么回事了，只要树的搜索往左支路怪，则更新一次cur就行了