Leetcode一百题——二叉搜索树中第k小的元素

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

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

• 树中的节点数为 n 。
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

‍
‍

题解：二叉搜索树中第 K 小的元素（中序遍历 + 数组法）

1. 算法核心思想：降维打击再现

这道题如果死盯着树形结构去数“谁是第 k 小”，大脑很容易绕晕。 但既然这是一棵二叉搜索树，我们完全可以对它进行“降维打击”：

1. 拍扁：利用 BST 的天生神力，对其进行中序遍历（左 -> 根 -> 右），把二维的树结构无损转换成一个一维的、严格单调递增的数组。
2. 取值：既然数组已经从小到大排好序了，那么“第 k 小的元素”，理所当然就是数组中索引为 k - 1 的那个元素。

‍
‍

2. 代码逻辑拆解

• 主控函数 kthSmallest：

  • 先做边界拦截（虽然题目通常会保证树不为空且 k 有效，但写上判空是极好的工程习惯）。注：C++ 中返回 NULL 其实就是返回 0，这里因为返回值要求是 int，更严谨的写法可以返回一个特定的错误码比如 -1。
  • 创建一个用于接收数据的数组 v。
  • 调用递归函数，将整棵树的值按顺序“装入”数组。
  • 直接精准狙击目标：返回 v[k - 1]。

• 辅助递归函数 func：

  • 标准的中序遍历模板，没有任何多余的动作。先一路向左探底找最小的，然后记录自己，再向右探测，完美保证了存入数组的数字是从小到大的。

‍

class 二叉搜索树种第k小的元素 {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (root == NULL) {
            return NULL;
        }

        vector<int> v;
        func(v, root);
        return v[k];
    }
    void func(vector<int>& v, TreeNode* node) {
        if (node == NULL) {
            return;
        }
        func(v, node->left);
        v.push_back(node->val);
        func(v, node->right);
    }
};

3. 复杂度分析

• 时间复杂度：O(N)。其中 N 是二叉搜索树的节点总数。因为你的代码会将树上的所有节点都遍历一遍并存入数组，耗时与节点数成正比。
• 空间复杂度：O(N)。为了把树“拍扁”，我们申请了一个长度为 N 的额外数组 v 来存储所有的节点值，加上递归产生的栈空间，总空间复杂度为 O(N)。

‍