跳到主要内容

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

· 阅读需 2 分钟

1、题干​

给定一棵二叉搜索树和其中的一个节点 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/

2、解题思路​

中序遍历记录前一节点pre，若前一节点与p引用相同，则当前节点node就是p的中序后继，记为res即最终返回结果。

3、代码​

var inorderSuccessor = function (root, p) {
    let pre, res = null;
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        if (pre === p) res = node;
        pre = node;
        dfs(node.right);
    }
    return dfs(root), res;
};

4、执行结果​

1.png