二叉搜索树的第k个结点

原文地址：https://www.jianshu.com/p/bc1fa1bb60b9

时间限制：1秒 空间限制：32768K

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

我的代码

/*
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==nullptr || k<1)
            return nullptr;
        int count=0;
        return KthNodeCore(pRoot,k,count);
    }
    TreeNode* KthNodeCore(TreeNode* pRoot, int k, int &count){
        if(pRoot==nullptr)
            return nullptr;
        TreeNode* res=KthNodeCore(pRoot->left,k,count);
        if(res)
            return res;
        if(++count==k)
            return pRoot;
        return KthNodeCore(pRoot->right,k,count);
    }
};

运行时间：4ms
占用内存：604k