九号球普通 2023年11月18日上午10:57

“`java
中序遍历倒叙
class Solution {
int res;
int cnt;
public int findTargetNode(TreeNode root, int cnt) {
this.cnt = cnt;
recur(root);
return res;
}

public void recur(TreeNode root) {
    if (root == null) {
        return;
    }
    recur(root.right);
    if (cnt <= 0) return;
    if (--cnt <= 0) {
        res = root.val;
        return;
    }
    recur(root.left);


}

}

0 赞同 0 条回复

招舟子普通 2023年8月26日下午4:02

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res=0,count=0;
public int kthLargest(TreeNode root, int k) {
count = k;
inorder(root);
return res;
}
void inorder(TreeNode root){
if(rootnull){
return;
}
inorder(root.right);
count–;
if(count0){
res = root.val;
}
inorder(root.left);
}
}
加油

0 赞同 0 条回复

jhfuture 普通 2023年8月15日下午9:06

“`java
时间复杂度和空间复杂度都为 O（n）
class Solution {
int k=0;
int target;
public int kthLargest(TreeNode root, int k) {
// 使用右根左
this.k=k;
right_root_left(root);
return target;
}
public void right_root_left(TreeNode root){
if(root==null||k<0){
return ;
}
right_root_left(root.right);
k--;
if(k==0){
target=root.val;
}
right_root_left(root.left);
}
}

0 赞同 0 条回复

CV大神普通 2023年7月20日上午10:26

 int target;
    int k;

    /**
     * 主要思路是：二叉搜索树的中序遍历是递增的，也就是[[左子树],根,[右子树]]，那么左右树互换下
     * [[右子树],根,[左子树]]就是递减的，所以变成了找第k个数
     */
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        search(root);
        return target;
    }

    public void search(TreeNode root){
        if(root == null)return;
        search(root.right);
        //不加的话会拦不住
        if(k == 0){
            return;
        }
        if(--k == 0){
            target = root.val;
            return;
        }
        search(root.left);
    }

0 赞同 0 条回复

断舍离永久会员 2023年7月13日上午10:01

class Solution {

    //全局k,用于更新
    int k = 0;

    //最后结果
    int result = -1;

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

    /*
    * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值
    * 
    * 可以使用中序遍历来做，中序遍历左中右是按照从小到大的顺序
    * 我们只需要更改递归顺序，变为右中左，就可以按照从大到小的顺序
    * 此时我们对k递减，当递减为0时，就是第k大的节点值
    * */
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.right);       //右
        if(--k == 0){
            result = root.val;
        }
        inOrder(root.left);        //左
    }
}

0 赞同 0 条回复

江畅普通 2023年7月11日下午6:53

// 二叉搜索树的第k大节点
// 时间复杂度 O(N)
// 空间复杂度 O(N)
class Solution {
private:
    int res;

    // 二叉搜索树的中序遍历，为从小到大的有序序列
    void dfs(TreeNode* root, int& k) {
        if (root == nullptr) {
            return;
        }
        dfs(root->right, k);
        --k;
        if (k == 0) {
            res = root->val;
            return;
        }
        dfs(root->left, k);
    }

public:
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return res;
    }
};

0 赞同 0 条回复

BOZ 普通 2023年7月11日下午1:14

【思路】递归思路，用中序遍历（右中左）即可得到二叉搜索树的从大到小排列
【复杂度】时间/空间复杂度均为平均O(logn)，最差O(n)

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        int result;
        function<void(TreeNode*)> _inTraverse = [&](TreeNode* root) {
            // traverse right child
            if(root->right != NULL) _inTraverse(root->right);
            if (k <= 0) return;
            // traverse root
            if (--k == 0) result = root->val;
            // traverse left child
            if(root->left != NULL) _inTraverse(root->left);
        };
        _inTraverse(root);

        return result;
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月10日下午4:28

时间复杂度O(N)
空间复杂度O(N)

class Solution {
    int id=0;
    int target=0;
    public int kthLargest(TreeNode root, int k) {

        id=k;
        rrl(root);

        return target;
    }
    public void rrl(TreeNode root){
        if(root==null||id<=0)return;

        rrl(root.right);

        id--;
        if(id==0){
            target=root.val;
        }
        rrl(root.left);
    }
}

0 赞同 0 条回复

Sexypig. 普通 2023年7月9日上午1:24

这段代码的功能是在给定的二叉树中找到第k大的节点值。
代码首先定义了一个二叉树节点的结构体，包含值、左子节点和右子节点。然后定义了一个Solution类，其中有一个成员函数kthLargest，用于找到第k大的节点值。
kthLargest函数首先调用了postOrder函数，对二叉树进行倒序的中序遍历。具体来说，先遍历右子树，然后遍历当前节点，最后遍历左子树。在遍历右子树的过程中，每遍历一个节点，将rank值加1。当rank等于k时，说明找到了第k大的节点，将该节点的值赋给res，并返回。在遍历左子树的过程中，同样进行相同的操作。
在主函数中，创建了一个二叉树，并调用了Solution类的kthLargest函数，将要找的第k大的节点值存储在result变量中。最后输出结果。
代码中还包含了释放内存的操作，将创建的节点逐个删除。
注：代码中的二叉树创建部分被注释掉了，可以根据需要取消注释并修改节点的值来创建不同的二叉树。

#include <iostream>
using namespace std;

// 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:
    int kthLargest(TreeNode *root, int k)
    {
        postOrder(root, k);
        return res;
    }
    int res = 0;
    int rank = 0;
    // 中序遍历,因为找第k大，所以需要倒序遍历
    //  先遍历右子树，从右往左数第k大
    void postOrder(TreeNode *root, int k)
    {
        if (root == nullptr)
            return;
        // 遍历右子树，直到达到最深处，即为最大开始往回找
        postOrder(root->right, k);
        ++rank;
        if (rank == k)
        {
            res = root->val;
            return;
        }
        postOrder(root->left, k);
    }
};

int main()
{
    // 创建二叉树
    // TreeNode* root = new TreeNode(5);
    // root->left = new TreeNode(3);
    // root->right = new TreeNode(6);
    // root->left->left = new TreeNode(2);
    // root->left->right = new TreeNode(4);
    // root->left->left->left = new TreeNode(1);
    TreeNode *root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);

    Solution solution;
    int k = 3; // 要找第k大的节点
    int result = solution.kthLargest(root, k);

    cout << "The " << k << "th largest element in the binary tree is: " << result << endl;

    // 释放内存
    // delete root->left->left->left;
    // delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

0 赞同 0 条回复

WhyNot 普通 2023年7月6日上午11:43

int kthLargest(struct TreeNode* root, int k){
    int* result = (int*)malloc(sizeof(int)*10000);
    int returnSize = 0;
    dfs(root,&returnSize,result);
    return result[returnSize-k];
}
void dfs(struct TreeNode* root,int *returnSize,int* result)
{
    if(root!=NULL)
    {
        dfs(root->left,returnSize,result);
        result[(*returnSize)++] = root->val;
        dfs(root->right,returnSize,result);
    }
    return;
}

时间复杂度是 O(N)
空间复杂度是 O(N)

0 赞同 0 条回复

mpweixin用户普通 2023年7月6日上午10:14

java
class Solution {
    private int k = 0; //纪录k
    private int target = -1; //纪录最终值，如果没有找到返回-1

    public int kthLargest(TreeNode root, int k) {
        //使用中序遍历，不过按照先右子树，根，左子树的顺序
        this.k = k;
        reverseInOrder(root);
        return target;
    }

    public void reverseInOrder(TreeNode root) {
        if(root == null || k <= 0) {
            return;
        } 

        reverseInOrder(root.right);
        k--;

        if(k == 0) {
            this.target = root.val;
        }

        reverseInOrder(root.left);
    }
}

空间复杂度和时间复杂度都是O(n)

0 赞同 0 条回复

残月冷骄阳普通 2023年7月5日下午7:41

迭代法实现

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
     return   midOrderMethod(root,k);

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

0 赞同 0 条回复

局外人普通 2023年7月5日上午9:46

思路：二叉搜索树按照中序遍历，其节点值是从小到大的。不过我们要找第k大节点，只需要将“左根右”遍历顺序变为“右根左”即可。
时间复杂度：O(n) 空间复杂度：O(n)

class Solution {
    //二叉搜索树，中序遍历，按顺序排列！
    int cnt = 0;
    int res = 0;
    public void InOrder(TreeNode root, int k){
        if(root==null)  return;

        InOrder(root.right, k);

        cnt++;
        if(cnt==k){
            res = root.val;
            return;
        }  

        InOrder(root.left, k);
    }
    public int kthLargest(TreeNode root, int k) {
        InOrder(root, k);
        return res;
    }
}

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午3:03

中序遍历

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

0 赞同 0 条回复

彦，，# 普通 2023年7月4日上午11:47

//中序感觉还是有点绕

int kthLargest(TreeNode* root, int k) {
        vector<int> ans;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while (cur != nullptr || !stk.empty()) {
            if (cur != nullptr) {
                stk.push(cur);
                cur = cur -> right;
            } else {
                cur = stk.top();
                stk.pop();
                if(--k == 0) return cur -> val;
                cur = cur -> left;
            }
        }
        return -1;
    }

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月2日下午5:13

时间复杂度：O(N)
额外空间复杂度：O(N)

class Solution {
    public int kthLargest(TreeNode root, int k) {
        // 中序遍历 - 顺序改为右中左
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            if(root != null) {
                stack.push(root);
                root = root.right;
            } else {
                root = stack.pop();
                k--;
                if(k == 0) return root.val;
                root = root.left;
            }
        }
        return 0;

    }
}

0 赞同 0 条回复

花老爷普通 2023年7月2日下午12:07

中序遍历的倒序：右中左
时间：O(n)
空间：O(n)

class Solution {
    private int cur = 0, ans = -1;

    public int kthLargest(TreeNode root, int k) {
        cur = k;
        postorderReverse(k, root);
        return ans;
    }

    private void postorderReverse(int k, TreeNode root) {
        if (cur <= 0 || root == null) {
            return;
        }
        postorderReverse(k, root.right);
        if (--cur == 0) {
            ans = root.val;
        }
        postorderReverse(k, root.left);
    }
}

0 赞同 0 条回复

小吕普通 2023年7月1日上午10:47

c++中序统一迭代
int kthLargest(TreeNode* root, int k) {
vectorvec;
stack<TreeNode>st;
if(root!=NULL)st.push(root);
while(!st.empty())
{
TreeNode temp = st.top();
if(temp!=NULL)
{
st.pop();
if(temp->right)st.push(temp->right);
st.push(temp);
st.push(NULL);
if(temp->left)st.push(temp->left);
}
else
{
st.pop();
temp = st.top();
st.pop();
vec.push_back(temp->val);
}
}
return vec[vec.size()-k];
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月1日上午12:32

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def count(self, root):
            if not root:
                return 0
            return self.count(root.left) + self.count(root.right) + 1

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:

        cnt = self.count(root.left)
        print(cnt)

        if cnt + 1 == k:
            return root.val
        elif cnt + 1 > k:
            return self.kthSmallest(root.left, k)
        else:
            return self.kthSmallest(root.right, k - cnt - 1)

记得helper function

0 赞同 0 条回复

行动派小彩笔普通 2023年6月30日下午8:28

// 通过vector保存中序遍历的反序列，直接return第k大的值
 // 时间O(n),空间O(n)
class Solution {
public:
    void dfs(TreeNode* root, vector<int>& v)
    {
        if(!root) return;
        dfs(root->right,v);
        v.push_back(root->val);
                dfs(root->left,v);
        return;
    }
    int kthLargest(TreeNode* root, int k) {
        vector<int> v;

        dfs(root,v);

        return v[k-1];
    }
};

1 赞同 0 条回复

怀瑾永久会员 2023年6月30日下午5:26

C++实现

#include <iostream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二叉搜索树的中序遍历
void inOrderTraversal(TreeNode* root, std::vector<int>& nodes) {
    if (root == nullptr) {
        return;
    }
    inOrderTraversal(root->left, nodes);
    nodes.push_back(root->val);
    inOrderTraversal(root->right, nodes);
}

int kthLargest(TreeNode* root, int k) {
    std::vector<int> nodes;
    inOrderTraversal(root, nodes);
    int n = nodes.size();
    return nodes[n - k];
}

int main() {
    // 构建二叉搜索树
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->left->left->left = new TreeNode(1);

    int k = 3;
    int result = kthLargest(root, k);
    std::cout << "The " << k << "th largest element is: " << result << std::endl;

    // 释放内存
    delete root->left->left->left;
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

0 赞同 0 条回复

Vow the vow。普通 2023年6月30日下午12:04

根据中序遍历有序的特点。

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

    // 右根左
    public void kthLargest(TreeNode node){
        if(node == null) return;
        if(k == 0) return;
        kthLargest(node.right);
        if(--k == 0) res = node.val;
        kthLargest(node.left);
    }

0 赞同 0 条回复

大鑫啊普通 2023年6月29日下午10:32

时空复杂度：O(n)
1、还是分析发现需要递归找到最大的节点，也就是右子树中最右边的节点
2、递归三部曲：确定递归函数的方法体，确定返回值，理清栈中递归前后的逻辑
3、第三点相对较难，可以思考到从最底层栈中返回时，递归函数返回的就是最大值，我们只用计数，然后返回等于零时的值

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

0 赞同 0 条回复

Jerry 普通 2023年6月29日下午10:23

// 后序遍历
public class Solution {
    int maxValueOfK; //第k大的元素
    int rank; // 记录当前元素的排名
    public int kthLargest(TreeNode root, int k) {
        traverse(root, k);
        return maxValueOfK;
    }

    void traverse(TreeNode root, int k) {
        if (root == null) {
            return;
        }

        traverse(root.right, k);
        rank++;
        if (rank == k) {
            // 找到第k大元素
            maxValueOfK = root.val;
            return;
        }
        traverse(root.left, k);
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

Yodl. 普通 2023年6月29日下午9:54

class Solution {
public:
    void find(TreeNode* root,vector<int>& ans)
    {
        if(root==NULL)
        {
            return;
        }
        find(root->left, ans);
        ans.push_back(root->val);
        find(root->right, ans);
        return;
    }
    int kthLargest(TreeNode* root, int k) {
        vector<int> ans;
        find(root, ans);
        return ans[ans.size()-k];
    }
};
//时间复杂度:O(n)，空间复杂度:O(logn)

0 赞同 0 条回复

yxy 普通 2023年6月29日下午8:16

复杂度O(n)

/**
 * 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:
    vector<int> v;
    void dfs(TreeNode* root)
    {
        if(!root) return;
        if(root->left)
            dfs(root->left);
        v.push_back(root->val);
        if(root->right)
            dfs(root->right);
    }
    int kthLargest(TreeNode* root, int k) {
        dfs(root);
        return v[v.size()-k];
    }
};

0 赞同 0 条回复

伏月三十普通 2023年6月29日下午7:49

时间复杂度，空间复杂度：O(n) 最差O(logn)

class Solution {
    int k=0;
    int target=0;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        right_root_left(root);
        return target;
    }

    private void right_root_left(TreeNode root){
        if(root == null || k<=0){
            return;
        }

        right_root_left(root.right);

        //打印当前节点
        k--; //打印一个就减一下
        if(k==0){
            target=root.val;
        }

        right_root_left(root.left);
    }
}

0 赞同 0 条回复

Ming 普通 2023年6月29日下午7:25

二叉搜索树的中序遍历是从小到大的数组，所以反过来是从大到小
每遍历一次k值减一，直到为0则此时结点为目标值

class Solution {
    int k = 0;
    int target = 0;
    public int kthLargest(TreeNode root, int k) {
        // 中序遍历：有序的序列 左 根 右 从小到大排序的
        //                      右 根 左 从大到小的排序
        this.k = k;
        reverseInorder(root);
        return target;
    }
    void reverseInorder(TreeNode root) {
        if(root == null || k < 0) return;

        reverseInorder(root.right);
        k--;
        if(k == 0) {
            target = root.val;
        }
        reverseInorder(root.left);
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月29日下午6:56

//从右往左中序遍历，第k个即为第k大结点
//时间O(n) 空间O(n)
class Solution {

    public int k;
    public int result = -1;

    public int kthLargest(TreeNode root, int k) {
        if(root == null){
            return -1;
        }

        this.k = k;

        kthLargest(root);

        return result;
    }

    public void kthLargest(TreeNode root){
        if(root == null){
            return;
        }

        //从右往左遍历中序遍历
        kthLargest(root.right);
        k--;
        if(k == 0 ){ //k减到零，正好遍历到第k个结点
            result = root.val;
            return;
        }
        if(result != -1){
            return;
        }
        kthLargest(root.left);
    }
}

0 赞同 0 条回复

désire. 普通 2023年6月29日下午4:34

C++实现：
class Solution {
public:
vector res;
void order(TreeNode* root)
{
if(root NULL) return;
order(root->left);
res.push_back(root->val);
order(root->right);
}
int kthLargest(TreeNode* root, int k)
{
if(root NULL) return -1;
order(root);
return res[res.size() – k];
}
};

0 赞同 0 条回复

张开怀普通 2023年6月29日下午3:59

class Solution{
public:
       int kthLargest(TreeNode* root, int k){
              int target = 0;
              right_root_left(root, k, target);
              return target;
       }

       void right_root_left(TreeNode* root, int &k, int &target){
              if(!root || k<=0) return ;
              right_root_left(root->right, k, target);
              // 打印当前根节点
              k--;
              if(k == 0){
                     target = root->val;
              }
              right_root_left(root->left, k , target);
       }
};

时间复杂度：最差为O(n)，平均为logn
空间复杂度：最差为O(n)，平均为logn

0 赞同 0 条回复

Dsjh 普通 2023年6月29日下午3:52

MY

// 右 中 左
class Solution {
public:
    vector res;
    int kthLargest(TreeNode* root, int k) {
        search(root,k);
        return res[k-1];
    }
    void search(TreeNode* root,int k){
        if(!root){
            return;
        }
        if(res.size()>k-1)
            return;
        search(root->right,k);
        res.push_back(root->val);
        serach(root->left,k);
    }
};;

0 赞同 0 条回复

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

共以下 32 个回答

迭代法实现

复杂度

Code

MY

# 回答此问题取消回复

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

共以下 32 个回答

迭代法实现

复杂度

Code

MY

# 回答此问题 取消回复

# 回答此问题取消回复