LeetCode 第285题：二叉搜索树中的顺序后继

📖 文章摘要

本文详细解析LeetCode第285题“二叉搜索树中的顺序后继”，这是一道考察二叉搜索树性质的中等难度题目。文章提供了递归和迭代两种实现方案，包含C#、Python、C++三种语言实现，配有详细的树遍历分析和性能对比。适合学习二叉搜索树和树遍历算法的读者。

核心知识点： 二叉搜索树、中序遍历、树的遍历
难度等级： 中等
推荐人群： 具备基础数据结构知识，想要提升树算法设计能力的开发者

题目描述

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

节点 p 的后继是值比 p.val 大的节点中值最小的节点。

示例

示例 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, 10^4] 内。
-10^5 <= Node.val <= 10^5
树中所有节点的值都是唯一的。

解题思路

本题可以使用两种方法来实现：

利用BST性质：
- 如果当前节点值小于等于p的值，则后继节点在右子树中
- 如果当前节点值大于p的值，则当前节点可能是后继节点，继续在左子树中寻找更小的后继
中序遍历：
- 进行中序遍历
- 记录前一个访问的节点
- 当前一个节点是p时，当前节点就是后继

图解思路

BST性质分析表

当前节点值	与p的关系	搜索方向	可能是后继
root.val <= p.val	小于等于	右子树	否
root.val > p.val	大于	左子树	是

中序遍历状态分析表

遍历顺序	当前节点	前一节点	是否找到p	操作
左子树	null	null	否	继续遍历
根节点	root	prev	是/否	更新prev
右子树	next	root	是/否	继续遍历

代码实现

C# 实现

public class Solution {
    public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        
        while (root != null) {
            if (p.val >= root.val) {
                root = root.right;
            } else {
                successor = root;
                root = root.left;
            }
        }
        
        return successor;
    }
}

Python 实现

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        successor = None
        
        while root:
            if p.val >= root.val:
                root = root.right
            else:
                successor = root
                root = root.left
                
        return successor

C++ 实现

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* successor = nullptr;
        
        while (root != nullptr) {
            if (p->val >= root->val) {
                root = root->right;
            } else {
                successor = root;
                root = root->left;
            }
        }
        
        return successor;
    }
};

执行结果

C# 实现

执行用时：88 ms
内存消耗：27.2 MB

Python 实现

执行用时：76 ms
内存消耗：18.6 MB

C++ 实现

执行用时：28 ms
内存消耗：22.8 MB

性能对比

语言	执行用时	内存消耗	特点
C#	88 ms	27.2 MB	代码结构清晰，性能适中
Python	76 ms	18.6 MB	代码最简洁，性能不错
C++	28 ms	22.8 MB	性能最优，内存占用适中

代码亮点

🎯 利用BST性质优化搜索
💡 无需额外空间的迭代实现
🔍 优雅处理边界情况
🎨 代码简洁易懂

常见错误分析

🚫 未考虑节点不存在的情况
🚫 错误理解中序后继定义
🚫 遍历方向选择错误
🚫 未正确更新后继节点

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
BST性质法	O(H)	O(1)	空间效率高	依赖BST性质
中序遍历法	O(N)	O(H)	思路直观	需要遍历全树
父指针法	O(H)	O(1)	实现简单	需要父指针

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第285题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

BST性质分析表

中序遍历状态分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流