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

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

难度中等60

给定一棵二叉搜索树和其中的一个节点 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 题相同： 力扣

根据中序遍历顺序。

有右子树，返回其最左边的节点；

无右子树，返回其根。

做法：

1. 有序列表先二分查找到节点p，有序列表如果查找节点在当前节点的左边，证明当前节点有可能是后继节点curr>p，记录当前节点为后继节点
2. 找到p后，如果有右子树，找到最左边的节点返回
3. 没有右子树，返回二分查找时的后继节点 prev > curr.right > p

/**
 * 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) {
        // 二分查找
        TreeNode curr = root;
        TreeNode prev = null;
        while (curr != p) {
            if (curr.val > p.val) {
                prev = curr;
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        // 右节点不为空
        if (curr.right != null) {
            curr = curr.right;
            while (curr.left != null) {
                curr = curr.left;
            }
            return curr;
        }
        return prev;
    }
}