LeetCode LCR 053. 二叉搜索树中的中序后继

Categories:

题目描述
思路分析
1. 解法一：利用 BST 性质（推荐）
相似题目

题目描述

✅ LCR 053. 二叉搜索树中的中序后继

思路分析

解法一：利用 BST 性质（推荐）

核心思路：

若 p 有右子树，后继是右子树的最左节点。

若 p 无右子树，从根开始搜索，遇到 p.val < cur.val 时记录后继并向左走，否则向右走。

搜索结束时记录的候选节点即为后继。

复杂度分析：

时间复杂度：O(h)，其中 h 表示树高。

空间复杂度：O(1)，仅使用常数额外指针。

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (p == null) {
            return null;
        }

        if (p.right != null) {
            TreeNode cur = p.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }

        TreeNode succ = null;
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val) {
                succ = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return succ;
    }
}

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
    if p == nil {
        return nil
    }

    if p.Right != nil {
        cur := p.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        return cur
    }

    var succ *TreeNode
    cur := root
    for cur != nil {
        if p.Val < cur.Val {
            succ = cur
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    return succ
}

相似题目

题目	难度	考察点
173. 二叉搜索树迭代器	中等	中序遍历
230. 二叉搜索树中第 K 小的元素	中等	BST
98. 验证二叉搜索树	中等	BST
450. 删除二叉搜索树中的节点	中等	BST
701. 二叉搜索树中的插入操作	中等	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/35651989