思路

题目分析

1. 题目给出了我们一个二叉搜索树
2. 我们要返回该树中第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* res;
    void inOrder(TreeNode*root,int &k){
        if(root==nullptr) return;		// 退出递归的返回条件之一：当前结点空
        inOrder(root->left,k);			// 先进行调用一次递归函数
        k--;							// 中序访问
        if(k==0) res=root;				// 判断是否拿到了第k个结点
        inOrder(root->right,k);			// 再进行一次递归调用
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        inOrder(pRoot, k);		// 递归函数传入节点指针 和 参数k
        return res;
    }
};

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历了所有节点，当然处理成在拿到第k个结点直接终止递归也可以，代码要再优化
• 空间复杂度：$O(logn)O(logn)$，递归函数占用内存栈的空间

方法二：迭代

• 采用栈的工具来帮助我们迭代
  • 方法如下
    • 首先沿着左子节点一直压栈
    • 压到最深处才取出栈顶元素，进行访问才是中序访问的位置
    • 最终再访问右子节点
  • 以上步骤构成循环

/*
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) {
        TreeNode* res = NULL;
        stack<TreeNode* > s;			  // 借助栈的工具
        int n = 0;						// 计数器
        TreeNode* cur = pRoot;			// cur指针标记一个根节点
        while(!s.empty() || cur) {		// 循环判断是否栈空，当前指针是否为空
            while(cur){					// 沿着左子节点一直压到底
                s.push(cur);
                cur = cur -> left;
            }
            cur = s.top();				// 中序访问的位置：取出栈顶元素
            s.pop();
            n++;						// 计数器更新
            if(n == k) {				// 判断是否拿到了第k个元素
                res = cur;
                return res;
            }
            cur = cur->right;			// 沿着右子节点继续访问
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O(k)O(k)$，访问k次即可
• 空间复杂度：$O(logn)O(logn)$，栈中最多的元素个数和树高一个量级