题解 | #二叉搜索树的第k个结点#

由于是二叉搜索树，所以一个结点左边的数都比该结点小，右边的数都比该结点大。 所以可以通过递归，按照中序遍历的顺序，先找到最左边的结点，该结点即为最小结点。然后开始计数，遍历到的第k个结点即为第k小结点。
这样做仅递归遍历了一次链表，大部分情况是不用遍历整个链表的，所以时间复杂度小于等于O(n)。递归过程中需要维护一个栈，空间复杂度等于O(logn)。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool start = false;
    int num = 0;
    TreeNode* result;
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(!pRoot || !k){
            return nullptr;
        }
        num = k;
        find(pRoot);
        return result;
    }
    void find(TreeNode *p){
        if(!p->left){
            start = true;
        }
        if(p->left){
            find(p->left);
        }
        if(start){
            num--;
            if(num == 0){
                result = p;
            }
        }
        if(p->right){
            find(p->right);
        }
    }
};