二叉搜索树第K小元素 · 多解法全解析

给定一个二叉搜索树（BST）的根节点 

二叉搜索树有着严格的“家族族规”：任何节点，其 

。基于这个特性，只要我们按照 

）去访问所有节点，读出来的数字序列 

关于这道题，我们提炼出了三大核心编码流派，带你从“暴力小白”一步步进阶为“大厂极客”。

完全不考虑提前停止。像抄作业一样，利用中序遍历把树里所有的数字全部抄到一个列表里。等整棵树抄完了，直接去列表里拿索引为 

心智负担极低，只需写出最标准的树遍历模板，直接交卷，不易出错。

严重浪费资源。哪怕只找第 1 小的数，它也要遍历 10000 个节点并申请相应的内存空间，时间空间复杂度均为 O(N)。

classSolution:
defkthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        res = [] # 准备一个空列表充当记事本

definorder(node):
if not node: return

            inorder(node.left)        # 1. 探底左子树
            res.append(node.val)      # 2. 不管三七二十一，全抄下来
            inorder(node.right)       # 3. 探底右子树

        inorder(root)
return res[k - 1] # 列表从 0 开始，所以取 k-1

这是上一流派的升级版。我们在遍历的过程中挂一个 

。每看一个数字，计数器减 1；当计数器归零时，说明已经找到了第 k 个数，立刻强行刹车，层层向上汇报，不再遍历剩下的树。

找到即停！如果 k 很小，程序可以在极短时间内下班，时间复杂度降为 O(H + k)，无需额外开辟大规模数组存放数据。

在递归逻辑中传递状态变量较为繁琐，初学者常常会在 Python 的全局变量定义或 C++ 的递归深度上踩坑。

🔥 源码展示（C++ & Python 双打版）：

// --- C++ 标准答案 ---
classSolution {
private:
int count = 0;
int result = 0;

public:
intkthSmallest(TreeNode* root, int k) {
        inorder(root, k);
return result;
    }

voidinorder(TreeNode* node, int k) {
// 如果节点为空，或答案已找到，立刻截断返回
if (node == nullptr || count >= k) return;

        inorder(node->left, k);   // 左

if (++count == k) {       // 中：计数器推进并验证
            result = node->val;
return;
        }

        inorder(node->right, k);  // 右
    }
};

# --- Python 纯净版 ---
classSolution:
defkthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.k = k
        self.result = None

defdfs(node):
# 这里必须用 is not None 严谨校验
if not node or self.result is not None:
return

            dfs(node.left)

            self.k -= 1
if self.k == 0:
                self.result = node.val
return

            dfs(node.right)

        dfs(root)
return self.result

面试官常常设下陷阱：“如果系统不允许深度递归，会引发爆栈，你该如何遍历？”。这套解法的核心是 

 来模拟计算机底层的递归调用路线。

代码相对难懂。思路是：一条死路往左走到黑，沿途将所有节点扔进桶（栈）中。撞墙后，从桶顶捞出最新放入的节点（即当前的极小值），记录并转向该节点的右侧继续。虽然复杂，但能展现你对计算机底层执行机制的深刻理解。

classSolution:
defkthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
while root or stack:
# 1. 疯狂往左钻，沿途留下记号在栈中
while root:
                stack.append(root)
                root = root.left

# 2. 撞南墙后，捞出最近的一个记号（当前最小节点）
            root = stack.pop()
            k -= 1
if k == 0:
return root.val

# 3. 转向该节点的右侧分支
            root = root.right


题目描述：给定一个二叉搜索树（BST）的根节点 root，和一个整数 k，请你设计一个算法查找其中 第 k 小 的元素（k 从 1 开始计数）。

算法

编程语言

二叉搜索树第K小元素解法大全：详解中序遍历天然有序特性，提供暴力收集、递归截断、非递归栈迭代三大流派。暴力法简单但效率低，递归法可提前终止最优，迭代法避免递归爆栈，附完整Python与C++代码，助你应对大厂面试。

Python

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

二叉搜索树第K小元素 · 多解法全解析

二叉搜索树第K小元素 · 多解法全解析

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐