跟着姚桑学算法-二叉搜索树的第k个结点

题. 二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第 k 小的结点。

你可以假设树和 k 都存在，并且 1≤k≤ 树的总结点数。

数据范围
树中节点数量 [1,500]。

样例

输入：root = [2, 1, 3, null, null, null, null] ，k = 3

    2
   / \
  1   3

输出：3

【题解】--- 递归剪枝

简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫 递归 。

以阶乘函数为例,如下, 在 factorial 函数中存在着 factorial(n - 1) 的调用，所以此函数是递归函数

publicintfactorial(int n){if (n < =1) {return1; }return n * factorial(n - 1)}

进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。

注意：

• 递归一定要有条件限定，保证递归能够停止下来，否则会发生栈内存溢出。
• 在递归中虽然有限定条件，但是递归次数不能太多。否则也会发生栈内存溢出。
• 构造方法,禁止递归

方法一：dfs(TreeNode* root, int& k)中把k作为参数传入同时加上引用&，相当于全局变量;

方法二：把k作为全局变量，就不用dfs递归的时候把k做参数传入同时加引用&，会更容易理解;

具体实现见代码注释。

复杂度分析：

时间复杂度为O(logn)。

C++代码实现：

// 方法一：dfs(TreeNode* root, int& k)中把k作为参数传入 同时加上引用&，相当于全局变量
// 中序遍历，看清 第k大还是第k小，第k大是 右中左，第k小是 左中右
class Solution {
public:
    int ans;
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return ans;
    }

    // 这里需要保证所有dfs函数共用一个k，加引用之后 k就相当于全局变量了
    void dfs(TreeNode* root, int& k){ // dfs函数返回值为void, 参数k要加引用&
        if (!root) return; // 搜索到叶子结点就返回
        dfs(root->right, k);           // 右
        if (k == 0) return;   // 利用k值进行剪枝
        if (--k == 0){                // 中
            ans = root->val;
            return;           // 剪枝
        }
        dfs(root->left, k);            // 左
    }
};

// 方法二：把k作为全局变量，就不用dfs递归的时候把k做参数传入同时加引用&，更好理解
class Solution {
public:
    int k, ans; //注意这里直接把 k 转变为全局变量，否则就要 在dfs(TreeNode* root, int& k)中把k作为参数传入 同时加上引用&
    int kthLargest(TreeNode* root, int _k) {
        k = _k;  // k 转化为全局变量
        dfs(root);
        return ans;
    }

    void dfs(TreeNode* root){
        if (!root) return; // 搜索到叶子结点就返回
        dfs(root->right);             // 右
        if (k == 0) return;   // 利用k值进行剪枝
        if (--k == 0){                // 中
            ans = root->val;
            return;           // 剪枝
        }
        dfs(root->left);             // 左
    }
};