LeetCode二叉搜索树中的中序后继

剑指 Offer II 053. 二叉搜索树中的中序后继

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

来源：LeetCode

利用二叉搜索树的性质解决。
对于某个节点来说，如果存在右子树，那么所要求的结果就是右子树里面的最左侧的节点（也就是中序遍历在该节点之后遍历到的）。
如果不存在右子树，那就找该节点的祖先节点，这个时候就可以用到搜索树的性质，如果搜索到当前节点值大于p节点的值，说明要找的节点可能在当前节点的左子树中，移动节点为左孩子，同时更新答案；如果大于，就移动为右孩子但不更新。

要注意第二种情况出现时，while循环结束的条件就是node为null，但是ans早已经更新完毕。

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