Inorder Successor in BST

其实道理很简单，每一个结点的后继必然是刚好比它大点的那个数，所以我们对目标节点进行搜索时如果发现当前节点比目标节点大，则把当前节点更新为后继，小则只遍历不用更新，这样就能求解

# 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
        """
        suc = None
        while root:
            if root.val > p.val:
                suc = root
                root = root.left
            else:
                root = root.right

        return suc

Java版本

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode result = null;
        while (root != null) {
            if (root.val > p.val) {
                result = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return result;
    }
}