面试题 04.06. 后继者

/**
 * 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(root == null){
            return null;
        }
        //1:第一步，找到一个大于P的节点
        //如果当前结点值 <= p，说明本节点包含其左子树，都不满足大于p，所以要去右子树找到第一个大于p的点
        if(root.val <= p.val){
            return inorderSuccessor(root.right,p);
        }
        //到这一步，说明找到了第一个大于p的点。
        //2:第二步，找到这个节点的最左的结点，也就是比P的并且是最小的点
        TreeNode ans = inorderSuccessor(root.left, p);
        //3：返回。如果ans已经null了，说明走到最左面了到头了，他的上一个结点root就是最左面的结点，则返回root
        if(ans == null){
            return root;
        }else {
            return ans;
        }
    }
}