CodingInterview-二叉搜索树的第K个结点

思路是对二叉搜索树进行中序遍历，中序遍历的顺序就是节点大小从小到大的顺序，所以只要在求得它的第 k 小的节点的时候返回即可。

下面是递归解法：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(k<=0) reutrn NULL;
        return this->findNode(pRoot,&k);
    }
    TreeNode* findNode(TreeNode* pNode,int* k){
        if(pNode==NULL) return NULL;
        TreeNode* left=this->findNode(pNode->left,k);
        if(left!=NULL) return left;
        if(--(*k)==0){
            return pNode;
        }
        TreeNode* right=this->findNode(pNode->right,k);
        return right;
    }
};

这里是循环版本。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot==NULL || k<=0) return NULL;
        stack<TreeNode*> s;
        TreeNode* cur=pRoot;
        while(cur!=NULL || !s.empty()){
            while(cur!=NULL){
                s.push(cur);
                cur=cur->left;
            }
            if(!s.empty()){
                cur=s.top();
                s.pop();
                if(--k==0) return cur;
                cur=cur->right;
            }
        }
        return NULL;
    }
};

最后不仅需要注意 pRoot 的边界情况，还要注意 k 的边界情况。