/*
题目：
求二叉搜索树的第k大节点。
*/
/*
思路：
中序遍历。
*/
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map> using namespace std; struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
}; TreeNode* KthNodeCore(TreeNode* pRoot, int &k){
TreeNode* target = nullptr; if(pRoot->left != nullptr){
target = KthNodeCore(pRoot->left,k);
}
if(target == nullptr){
if(k == 1){
target = pRoot;
}
k--;
}
if(target == nullptr && pRoot->right != nullptr){
target = KthNodeCore(pRoot->right,k);
}
return target;
} TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot == nullptr && k <= 0){
return nullptr;
}
return KthNodeCore(pRoot,k);
}