/*

题目：

	求二叉搜索树的第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);

}