【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点-跟着帅地玩副业，开拓第二曲线PlayOffer

Miracle· 普通 2023年9月16日下午3:32

时间复杂度o(n),空间复杂度o(n)
int ans;
int kthLargest(TreeNode* root, int k) {
dfs(root, k);
return ans;
}

void dfs(TreeNode* root, int& k){
if(!root) return;
dfs(root->right, k);
–k;
if(k 0) {
ans = root->val;
return;
}
dfs(root->left, k);
}

0 赞同 0 条回复

Sheng 永久会员 2023年8月31日下午4:48

第k大元素，以右中左非递归遍历找。

    public int kthLargest(TreeNode root, int k) {
        if(root == null) return 0;

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = root;
        int tmp = k;
        while(node != null || !stack.isEmpty()) {
            if(node != null) {
                stack.push(node);
                node = node.right;
            }
            else {
                node = stack.pop();
                tmp--;
                if(tmp == 0) return node.val;
                node = node.left;
            }
        }
        return 0;   
    }

0 赞同 0 条回复

小肸永久会员 2023年8月30日上午9:51

class Solution {
    //时间复杂度O(N)，最坏情况是需要取最后一个大的元素
    static int res = -1;
    //count用来计数右 | 中 | 左这是第几个节点，
    //使用类变量，不能在函数中传参，否则会回溯
    static int count = 0;
    public int kthLargest(TreeNode root, int k) {
        //leetcode中类变量还得在函数初始化一次，否则出bug
        res = -1;
        count = 0;
        dfs(root, k);
        return res;
    }
    private void dfs(TreeNode node, int target) {
        if (res != -1 || node == null) {
            return;
        }
        if (node.right != null) {
            dfs(node.right, target);
        }
        count ++;
        // System.out.println(1);
        if (count == target) {
            // System.out.println(node.val);
            res = node.val;
            return;
        }
        if (node.left != null) {
            dfs(node.left, target);
        }
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月28日下午11:41

中序遍历后的倒数第k位即是所求

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 中序遍历后的倒数第k位即是所求
    int kthLargest(TreeNode* root, int k) {
        vector<int> space;
        inorder(root, space);
        reverse(space.begin(), space.end());
        return space[k-1];
    }
    TreeNode* inorder(TreeNode* root, vector<int>& space){
        if(root==NULL){
            return NULL;
        }
        inorder(root->left, space);
        space.push_back(root->val);
        inorder(root->right, space);
        return root;
    }
};

0 赞同 0 条回复

sincere 普通 2023年8月27日下午10:20

思路：二叉搜索树的中序遍历肯定是递增序列，反过来就是递减序列，求第K大节点即中序遍历反过来的第K个
复杂度：时间复杂度O(n)，空间复杂度O(n)

class Solution {
    int res, k;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root) {
        if (root == null || k == 0) {
            return;
        }
        dfs(root.right);
        if (--k == 0) {
            res = root.val;
            return;// 已经找到就不需要再继续遍历了
        }
        dfs(root.left);
    }
}

0 赞同 0 条回复

帝心引力永久会员 2023年8月24日下午3:36

时间o(n), 空间o(n)
class Solution {
public:
    vector<int> inOrderVector;
    void inOrder(TreeNode* root){
        if(root == NULL) return;
        inOrder(root->left);
        inOrderVector.emplace_back(root->val);
        inOrder(root->right);
    }
    int kthLargest(TreeNode* root, int k) {
        inOrder(root);
        int n = inOrderVector.size();

        return inOrderVector[n - k];
    }
};

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月22日下午11:02

打卡

class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root){
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}

0 赞同 0 条回复

JustRtn 普通 2023年8月22日下午11:01

二叉树中序遍历变种，左中右 > 右中左

class Solution {
public:
    int f(TreeNode* root, int& k) {
        if (root == nullptr) {
            return -1;
        }
        int val = f(root->right, k);
        if (val != -1) {
            return val;
        }
        if (!--k)
            return root->val;
        val = f(root->left, k);
        if (val != -1) {
            return val;
        }

        return -1;
    }

    int kthLargest(TreeNode* root, int k) {
        return f(root, k);
    }
};

0 赞同 0 条回复

c 普通 2023年8月22日下午11:00

根据右中左便利

int res;
    int k;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        fun(root);
        return res;
    }
    public void fun(TreeNode root){
        if (root==null){
            return ;
        }
        fun(root.right);
        if(k == 0) return;
        if (--k==0){
            res = root.val;
        }
        fun(root.left);
    }

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月22日下午5:54

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Stack stack = new Stack<>();
        TreeNode p = root;
        int ans = 0;
        //右根左进行遍历
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.right;
            } else {
                p = stack.pop();
                //判断是否为第k大
                k--;
                if (k == 0) {
                    ans = p.val;
                    break ;
                }
                p = p.left;
            }
        }
        return ans;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月22日下午5:37

1、反向中序遍历，非递归

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(root != null || !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.right;
            }else{
                if(--k == 0){
                    return stack.peek().val;
                }
                root = stack.pop().left;
            }
        }
        return 0;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月22日下午1:47

 // 反向中序，时间O(n),空间O(n)
class Solution {
public:
    void dfs(TreeNode* root,int &ans,int &k)
    {
        if(!root||k<=0) return;
        dfs(root->right,ans,k);
        k--;
        if(k==0) ans=root->val;
        dfs(root->left,ans,k);
    }
    int kthLargest(TreeNode* root, int k) {
        int ans =0;
        dfs(root,ans,k);
        return ans;
    }
};

0 赞同 0 条回复

【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点

共以下 12 个回答

# 回答此问题取消回复

【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点

共以下 12 个回答

# 回答此问题 取消回复

# 回答此问题取消回复