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

思路： 根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第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);
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        midOrder(pRoot, k);
        return res;
    }
};

复杂度分析：

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

方法二：非递归中序遍历 具体做法： 用栈记录当前结点，不断往左深入，直到左边子树为空，再弹出栈顶（即为当前子树的父结点），然后再访问其右子树，其中每棵子树都遵循左中右的次序。

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(pRoot == NULL)
            return NULL;
        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;
			}
			pRoot = p->right;
		}
        return NULL;
    }
};

复杂度分析：

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