D : B DS二叉排序树_树中第k小的元素

Description

给定一个二叉排序树和一个整数k，要求输出树中第k个最小元素(k从1开始计数)。

Input

第一行输入t，表示有t个测试样例。
第二行起，首先输入n，接着输入n个整数表示一个二叉排序树，接着输入k。
以此类推共输入t个测试样例。
数组形式的二叉树表示方法与题目：DS二叉树_伪层序遍历构建二叉树 相同，输入-1表示空结点。

Output

每一行输出当前二叉排序树的第k个最小元素。
共输出t行。

Sample

#0

Input

4

5
3 1 4 -1 2
1

8
5 3 6 2 4 -1 -1 1
3

1
1
1

7
55 36 72 15 37 58 79
6

Output

1
3
1
72

Hint

设树中的结点数目为m。
1 <= k <= m
1 <= 结点值

AC代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉排序树节点
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int data) {
    if (root == nullptr) {
        return new TreeNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    }
    else {
        root->right = insert(root->right, data);
    }

    return root;
}

//在二叉排序树中，第一小的数一定在最左下角，其次第二小的数就是第一小的数的爹结点，第三小的数则是第三小的兄弟结点
// 正好符合了中序遍历的顺序
// 中序遍历并将结果存储在数组中
void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root != nullptr) {
        inorderTraversal(root->left, result);
        result.push_back(root->data);
        inorderTraversal(root->right, result);
    }
}

// 寻找树中第k个最小元素
int kthSmallest(TreeNode* root, int k) {
    vector<int> result;
    inorderTraversal(root, result);
    return result[k - 1];
}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; ++i) {
        int n;
        cin >> n;

        TreeNode* root = nullptr;

        for (int j = 0; j < n; ++j) {
            int data;
            cin >> data;
            if (data == -1)continue;
            root = insert(root, data);
        }

        int k;
        cin >> k;

        int kth = kthSmallest(root, k);
        cout << kth << endl;
    }

    return 0;
}