题意概括

给定一个二叉搜索树 (BST) 和一个整数 k，要求找到该树中第 k 个最小的元素。计数从 1 开始。

输入格式:

• 第一行为节点数量 n（包括空节点）。
• 第二行为 n 个整数，表示树的层序遍历序列，用 -1 代表空节点。
• 第三行为一个整数 k。

输出格式:

• 输出第 k 小的元素的值。

基础知识

本题的核心在于利用 二叉搜索树 (Binary Search Tree, BST) 的一个关键性质：中序遍历 (In-order Traversal) 一个 BST，会得到一个升序的节点值序列。

中序遍历 的顺序是：左子树 -> 根节点 -> 右子树。

因此，寻找 BST 中第 k 小的元素，就等价于寻找其中序遍历序列中的第 k 个元素。

我们可以通过一个递归的深度优先搜索 (DFS) 来实现中序遍历。在遍历过程中，我们维护一个计数器（可以直接使用 k），每访问一个节点（在访问完其左子树之后），就将计数器减一。当计数器减到 0 时，当前访问的节点就是我们要找的第 k 小的节点。

算法步骤如下：

1. 根据输入的层序遍历序列，构建二叉搜索树。
2. 设计一个递归函数 dfs(node) 来执行中序遍历。
3. 在 dfs 函数中，按 左 -> 根 -> 右 的顺序进行。
4. 访问“根”节点时，将 k 减 1。
5. 如果 k 变为 0，说明找到了目标，记录下当前节点的值并可以提前终止遍历。

该算法的时间复杂度主要由建树和遍历构成，均为 $O(N)$，所以总时间复杂度为 $O(N)$。空间复杂度为 $O(H)$（树的高度），用于递归栈，最坏情况下为 $O(N)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// 节点结构体
struct Nde {
    int v;
    Nde *l, *r;
    Nde(int val) : v(val), l(nullptr), r(nullptr) {}
};

int k, ans;

// 中序遍历 (DFS)
void dfs(Nde* u) {
    // 如果节点为空，或者已经找到答案，则返回
    if (!u || ans != -1) {
        return;
    }

    // 1. 遍历左子树
    dfs(u->l);

    // 2. 访问根节点
    k--;
    if (k == 0) {
        ans = u->v;
        return;
    }

    // 3. 遍历右子树
    dfs(u->r);
}

void run() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    if (n == 0 || a[0] == -1) {
        return;
    }

    // 使用队列通过层序遍历结果建树
    Nde* rt = new Nde(a[0]);
    queue<Nde*> q;
    q.push(rt);

    int i = 1;
    while (!q.empty() && i < n) {
        Nde* cur = q.front();
        q.pop();

        if (i < n && a[i] != -1) {
            cur->l = new Nde(a[i]);
            q.push(cur->l);
        }
        i++;

        if (i < n && a[i] != -1) {
            cur->r = new Nde(a[i]);
            q.push(cur->r);
        }
        i++;
    }
    
    cin >> k;
    ans = -1; // 初始化答案为一个无效值
    dfs(rt);
    cout << ans << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
5
3 1 4 -1 2
1
(修正: n应为5)
输出:
1

样例 2:
输入:
8
5 3 6 2 4 -1 -1 1
3
(修正: n应为8)
输出:
3
*/