从「第 K 小」这道题，看懂二叉搜索树的灵魂

别急着写代码

——从「第 K 小」这道题，看懂二叉搜索树的灵魂

先说一句很多人不爱听、但非常重要的话：

这道题考的不是技巧，而是你到底懂不懂二叉搜索树。

如果你真的懂 BST，这题会让你觉得——
“哦，就该这么解”。

如果你不懂，那你会：

• 写一堆 if else
• 用数组存一遍
• 或者靠运气刚好 AC

但心里没底。

一、引子：这题为什么老是考？

题目很简单：

给定一个二叉搜索树，找出其中第 K 小的元素。

很多同学第一反应是：

“这不就是排序吗？”

对，但也不对。

如果你把 BST 当成普通二叉树，
那你就已经输在起跑线上了。

二、先别写代码，咱用一句人话理解 BST

二叉搜索树（BST）有一个非常“朴素但致命”的性质：

左子树所有节点 < 根节点 < 右子树所有节点

而这个性质，直接