题解ACM模式 二叉搜索树的第k个节点

#include<iostream>

using namespace std;

struct TreeNode
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
	TreeNode(int x) :val(x), left(nullptr), right(nullptr) {}
};

TreeNode* insertBST(TreeNode* root, int val) {
	if (!root) return new TreeNode(val);
	if (val < root->val) root->left = insertBST(root->left, val);
	else root->right = insertBST(root->right, val);
	return root;
}

void MidOrder(TreeNode* root, int& k, int& res) {
	if (root == nullptr || k <= 0) return;
	MidOrder(root->left, k, res);
	k--;
	if (k == 0) {
		res = root->val;
		return;
	}
	MidOrder(root->right, k, res);
}

int main() {
	int n;
	TreeNode* root = nullptr;
	while (cin >> n) {
		root = insertBST(root, n);
		if (cin.get() == '\n') break;
	}
	int k;
	cin >> k;
	int res = 0;
	MidOrder(root, k, res);
	cout << res;
	return 0;
}