题目主要信息：

• 给定一棵结点数为n二叉搜索树，需要其中的第k小的TreeNode结点值
• 返回第k小的节点值即可
• 不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
• 保证n个节点的值不一样

思路：

根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第k个小的结点即可。 中序遍历有两种方式。

方法一：递归中序遍历

具体做法：

另写一函数进行递归中序遍历，设置全局变量count记录遍历了多少个结点，res记录第k个结点。

class Solution {
public:
    TreeNode* res = NULL;//记录返回的结点
    int count = 0;//记录中序遍历了多少个
    
    void midOrder(TreeNode* root, int k){
        if(root == NULL || count > k) //当遍历到结点为空或者超过k时，返回
            return;
        midOrder(root->left, k);
        count++;
        if(count == k)  //只记录第k个
            res = root;
        midOrder(root->right, k);
    }
    
    int KthNode(TreeNode* proot, int k) {
        midOrder(proot, k);
        if(res)
            return res->val;
        else //二叉树为空，或是找不到
            return -1;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，所有结点遍历一遍
• 空间复杂度：$O(n)O(n)$，栈空间最大深度

方法二：非递归中序遍历

具体做法：

用栈记录当前结点，不断往左深入，直到左边子树为空，再弹出栈顶（即为当前子树的父结点），然后再访问其右子树，其中每棵子树都遵循左中右的次序。

class Solution {
public:
    int KthNode(TreeNode* proot, int k) {
        if(proot == NULL)
            return -1;
        int count = 0;  //记录遍历了多少个数
        TreeNode* p = NULL;
        stack<TreeNode*> s;   //用栈辅助建立中序
        while (!s.empty() || proot != NULL) {
            while (proot != NULL) {
                s.push(proot);
                proot = proot->left;   //中序遍历每棵子树从最左开始
            }
            p = s.top();
            s.pop();
            count++;
            if (count == k) { //第k个直接返回
                return p->val;
            }
            proot = p->right;
        }
        return -1;//没有找到
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，每个结点遍历一遍
• 空间复杂度：$O(n)O(n)$，栈空间最大值