程序员面试金典-面试题 04.06. 后继者

题目：

https://leetcode-cn.com/problems/successor-lcci/

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

2
/
1 3

输出: 2
示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

5
/
3 6
/
2 4
/
1

输出: null

分析：

如果指定节点有右子树的话，那么它的后继一定在它的右子树中，且是右子树中的最小值，也就是最左孩子。

如果指定节点没有右子树的话，那么我们就要从根节点开始找到这个指定节点作为左孩子的父结点或者是所在左子树中的父结点。

遍历时如果当前结点值大于指定节点值，那么就去当前结点的左子树搜索，并且更新其父结点的值。否则就去右子树搜索。

程序：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(p.right != null){
            p = p.right;
            while(p.left != null){
                p = p.left;
            }
            return p;
        }
        TreeNode prev = null;
        TreeNode cur = root;
        while(cur.val != p.val){
            if(cur.val > p.val){
                prev = cur;
                cur = cur.left;
            }else{
                cur = cur.right;
            }
        }
        return prev;
    }
}