LeetCode刷题【剑指 Offer II 053】二叉搜索树中的中序后继

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

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

示例 1：

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

示例 2：

输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

提示：

• 树中节点的数目在范围 [1, 104] 内。
• -105 <= Node.val <= 105
• 树中各节点的值均保证唯一。

注意：本题与主站 285 题相同： https://leetcode-cn.com/problems/inorder-successor-in-bst/

题解

一看题目，二叉搜索树、中序后继这两个关键词，那么好说直接先上个中序遍历，记录下上一次访问的节点，如果上次的节点是目标节点，则当前访问到的节点就是这个节点的中序后继节点。

如果想要优化则需要对状态严格判断下需要中断的条件，容易疏漏，和这题思路一样。LeetCode刷题【面试题04.06】 后继者。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode target;
    TreeNode lastVisited;
    TreeNode follower;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        target = p;
        dfs(root);
        return follower;
    }

    private void dfs(TreeNode root){
        if (root == null || follower!=null) {
            return;
        }
        dfs(root.left);
        //中序
        if (follower==null && lastVisited!= null && lastVisited.val == target.val){
            follower = root;
        }
        lastVisited = root;
        dfs(root.right);
    }
}

那么再看下，本题中给出的是确定的一棵二叉搜索树，根据二叉搜索树的特性，左节点比根节点小，根节点比右节点小。可以根据这个条件来查找目标节点p。

找到p之后就需要再找到他的后继节点，分两种情况

• 假如p节点有右子节点，从p节点的右子节点开始往下找出最大的节点，即从右子树上最左边的节点。
• 假如p节点在某个节点的左子树上，那么他的后继节点也可能是这个左子树的根节点，即最后一次往左子树上寻找p节点的时候的那个节点。
• 右子节点的判定需要在左子树的判断优先级之上，因为BST的特性左子树上节点最小也比根节点小。

所以，代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    TreeNode lastBigger;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return dfs(root,p);
    }

    private TreeNode search(TreeNode root, TreeNode p){
        if (root.val == p.val){
            //如果有右子树，找出右子树中最大的
            if (root.right != null){
                TreeNode node = root.right;
                while (node.left != null){
                    node = node.left;
                }
                return node;
            }else{
                //如果没有右子树,则找到之前记录的比他大的后继节点中最小的
                return lastBigger;
            }
        }else{
            if (root.val > p.val){
                //这个节点比p节点大，记录下来
                lastBigger = root;
                return dfs(root.left,p);
            }else{
                return dfs(root.right,p);
            }
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)