题目

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

题解

**二叉搜索树的中序遍历是递增数组，那么二叉搜索树的中序遍历的倒序是递减数组。**利用这个性质，只需要进行中序遍历的倒序就可以

1.中序遍历倒序法（递归）

  • 时间复杂度$O(N)$
  • 空间复杂度$O(N)$，递归使用
class Solution {//两个方法。1.中序遍历倒序法（递归）
    int res;//结果
    int global_k;//类的私有变量使该变量在递归的全局起作用
    int end_flag = false;//结束递归的标志
public:
    int kthLargest(TreeNode* root, int k) {
         global_k = k;
         dfs(root);
         return res;

    }
    void dfs(TreeNode* node){
        if(!node) return;
        if(end_flag) return;//结束递归
        dfs(node->right);//递归右子树
        
        //中间节点的处理
        global_k--;
        if(global_k == 0){
            res = node->val;
            end_flag = true;
        }

        dfs(node->left);//递归左子树
    }
};

2.中序遍历倒序法（非递归）

  • 时间复杂度$O(N)$
  • 空间复杂度$O(1)$
class Solution {//两个方法。2.中序遍历倒序法（非递归）
public:
    int kthLargest(TreeNode* root, int k) {
        stack<TreeNode*> s;
        auto cur = root;
        while(cur || !s.empty()){
            while(cur){
                s.push(cur);
                cur = cur->right;
            }
            cur = s.top(); s.pop();
            //和中序遍历唯一的区别，不存入数组，到第k个数直接返回
            if(--k == 0) return cur->val;
            cur = cur->left;
        }
        return INT_MIN;
    }
};