ppopp 普通 2023年8月20日下午2:28

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

//遍历+对每个结点进行判断，判断时机参考中序遍历，k–，当k = 0时即跳出循环不再继续，保留循环之前的res
//递归，为了不让res和cur空间因为递归调用结束被回收，故定义为全局变量
//
class Solution {
private:
int res;
int cur;

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

void check(TreeNode* root, int k){
    if(!root || k == 0) return;  

    check(root->right, k);
    cur--;
    if(cur==0){
        res = root->val;
    }
    check(root->left, k);
}

};

0 赞同 0 条回复

hi 普通 2023年8月11日上午9:35

中序遍历倒序先得到大的值
k 逐次递减，等于0时得到答案

/**
 * 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:
    TreeNode* ans;

    int kthLargest(TreeNode* root, int k) {
    //二叉搜索树中序遍历（左、根、右）结果是递增的顺序，这样直接求第k 小的数
    //但要求是第K 大的数所以改一下顺序（右、根、左），每次k--，但k == 0 时节点值为答案
        dfs(root, k);
        return ans->val;
    }
    void dfs(TreeNode* p, int& k){
        if(!k || !p) return;
        dfs(p->right, k);
        k--;
        if(k == 0) ans = p;
        else dfs(p->left, k);
    }
};

0 赞同 0 条回复

山川湖海普通 2023年8月3日下午9:58

二叉搜索树的第k大节点 cpp
/**
* 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 res;
void dfs(TreeNode* root, int &k) {
    if (!root) return;
    dfs(root->right, k);
    k --;
    if (k == 0) {
        res = root->val;
        return;
    }
    dfs(root->left, k);
}

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

};

0 赞同 0 条回复

doordie. 普通 2023年7月27日下午4:12

递归逆序中序遍历

class Solution {
     // 计数
    int k = 0;
    // 返回结果
    int result;
     public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return  result;

    }

     void dfs(TreeNode root) {
        if (root == null){
            return;
        }
        dfs(root.right);
        if (k == 0){
            return;
        }
        if(--k == 0){
            result = root.val;
        }
        dfs(root.left);

    }
}

0 赞同 0 条回复

小季同学普通 2023年7月27日上午9:50

ts

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function kthLargest(root: TreeNode | null, k: number): number {
    // 边界判断
    if(!root) {
        return -1
    }
    // 中序遍历,递减
    const result: number[] = []
    function pretraverse(node: TreeNode) {
        if(!node) {
            return
        }
        pretraverse(node.left)
        result.push(node.val)
        pretraverse(node.right)
    }

    pretraverse(root)
    const list = result.reverse()
    return list[k-1]
};

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月22日下午11:08

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int k =0;
    int target = 0;
    public int kthLargest(TreeNode root, int k) {
        // 中序遍历 左 根 右 （从小到大）
        //          右 根 左
        this.k = k;
        right_root_left(root);
        return target;
    }

    void right_root_left(TreeNode root){
        if(root==null||k<=0) return;
        right_root_left(root.right);
        // 打印当前元素
        k--;
        if(k==0){
            target = root.val;
            return;
        }
        right_root_left(root.left);
    }
}

时间复杂度：平均O（logn）最差 O（n）
空间复杂度：平均O（logn）最差 O（n）

0 赞同 0 条回复

CKX 普通 2023年7月22日下午5:58

func kthLargest(root *TreeNode, k int) int {
    traverse := func(node *TreeNode){}
    res, rank := 0, 0

    traverse = func(node *TreeNode) {
        if node == nil {
            return
        }
        traverse(node.Right)
                /* 中序遍历代码位置 */
        rank++
        if k == rank {
            res = node.Val
            return
        }
                /*******************/
        traverse(node.Left)
    }
    traverse(root)
    return res
}

O(n)

0 赞同 0 条回复

片言莫语普通 2023年7月21日下午10:55

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
      int k = 0;    //表示第k个
      int target = 0;   //存放目标数
        public int kthLargest(TreeNode root, int k){
            this.k = k;
            right_root_left(root);  //右左根遍历 得到结点的由大到小的排列
            return target;
        }
        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 条回复

北辰普通 2023年7月21日下午8:11

class Solution {
    public static int kthLargest(TreeNode root, int k) {
        //中序遍历二叉搜索树直接接可以得到啊第k大元素
        List<Integer> ans = inorderTravel(root);
        return ans.get(ans.size()-k);
    }

    public static List<Integer> inorderTravel(TreeNode root){
        List<Integer> ans = new ArrayList<>();
        if(root==null) return ans;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null||!stack.isEmpty()) {
            if(cur!=null) {
                stack.push(cur);
                cur=cur.left;
            }else {
                TreeNode node = stack.pop();
                ans.add(node.val);
                cur = node.right;
            }
        }
        return ans;
    }
}

思路：中序遍历二叉搜索树得到是一个递增的序列，直接可得第k大元素的值是多少

0 赞同 0 条回复

普通 2023年7月19日下午11:22

c++ 代码中序遍历为有序数组
class Solution {
vector v;
int count;
public:
int kthLargest(TreeNode* root, int k)
{
dfs(root);
return v.at(v.size()-k);
}
void dfs(TreeNode* root)
{
if(!root) return;

    if(root->left) dfs(root->left); 
     v.push_back(root->val);
    if(root->right) dfs(root->right);
}

};

0 赞同 0 条回复

mpweixin用户普通 2023年7月19日下午7:59

class Solution {
    //BST的中序遍历递增
    List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        inOrder(root);
        return list.get(list.size()-k);
    }

    public void inOrder(TreeNode root) {
        if (root==null)
            return;
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }
}

0 赞同 0 条回复

枫梓。普通 2023年7月19日下午2:21

class Solution {
private:
    vector<int> ans;
public:
    int kthLargest(TreeNode* root, int k) {
        //中序遍历为正序
        traverse(root);
        int size = ans.size();
        return ans[size - k];
    }
    void traverse(TreeNode *root) {
        if(root->left) traverse(root->left);
        ans.push_back(root->val);
        if(root->right) traverse(root->right);
    }
};

二叉搜索树中序遍历即为正序排序结果，那么中序遍历即可。双O(n)

0 赞同 0 条回复

Marshan 普通 2023年7月19日下午2:16

中序遍历

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        vector<int> res;
        helper(res,root);
        // for(auto it:res){
        //     cout<<it<<endl;
        // }
        return res[res.size() - k];
    }
    void helper(vector<int> &res,TreeNode* root){
        if(root == nullptr){
            return;
        }
        helper(res,root->left);
        res.push_back(root->val);
        helper(res,root->right);
    }
};

0 赞同 0 条回复

Mby 普通 2023年7月19日下午1:19

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int k = 0;
    int target = 0;
    public int kthLargest(TreeNode root, int k) {
        //中序遍历  右根左 从大到小排序
        this.k = k;
        right_root_left(root);
        return target;
    }
    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 条回复

土豆芋泥包_ 普通 2023年7月18日下午9:05

代码

class Solution {
    int k=0;
    int target;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        right_root_left(root);
        return target;
    }
    //中序遍历——右 根 左 打印
    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 条回复

人生何处不青山普通 2023年7月18日下午5:00

简单题

function kthLargest(root: TreeNode | null, k: number): number {
    let cur = 1;
    let res = root.val;
    function dfs(node: TreeNode | null): void {
        if(!node) return;
        dfs(node.right);
        if(cur++ === k) res = node.val;
        dfs(node.left);
    }
    dfs(root);
    return res;
};

0 赞同 0 条回复

CaCO3 永久会员 2023年7月18日上午11:47

”’java
class Solution {
public int kthLargest(TreeNode root, int k) {
//二叉搜素：中序遍历
List list = new ArrayList<>();
inOrder(root,list);
return list.get(k-1);
}

//中序遍历代码
private void inOrder(TreeNode root,List<Integer> list){
    if(root == null){
        return;
    }
    inOrder(root.right,list);
    list.add(root.val);
    inOrder(root.left,list);
}

}
时间复杂度O(n)
空间复杂度O(n)
”’

0 赞同 0 条回复

NullPointerException 普通 2023年7月18日上午11:25

class Solution {
List list =new ArrayList();
public int kthLargest(TreeNode root, int k) {
//二叉搜索树前序遍历就是递增的
bianli(root);
return list.get(k-1);
}
public void bianli(TreeNode root)
{
if(root null)
{
return ;
}

    bianli(root.left);
    list.add(0,root.val);
    bianli(root.right);


}

}

0 赞同 0 条回复

wonderful 普通 2023年7月17日下午11:36

深度优先遍历

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def dfs(root):
if not root: return
dfs(root.right)
if self.k 0: return
self.k -= 1
if self.k 0: self.res = root.val
dfs(root.left)

    self.k = k
    dfs(root)
    return self.res

0 赞同 0 条回复

周小二普通 2023年7月17日下午10:45

//代码
class Solution {
    private int k;
    private int i;
    private int result;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return result;
    }

    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.right != null) dfs(root.right);
        if(--k == 0) {
            result = root.val;
            return;
        }
        if(root.left != null) dfs(root.left);
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月17日下午10:41

第k大，是右根左

class Solution {
    int res = 0, cnt = 0;
    public int kthLargest(TreeNode root, int k) {
        dfs(root,k);
        return res;
    }

    public void dfs(TreeNode root, int k) {
        if(root == null) return;
        dfs(root.right,k);
        if(++ cnt == k) {
            res = root.val; 
        }
        dfs(root.left,k);
    }
}

0 赞同 0 条回复

June 普通 2023年7月17日下午10:06

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 //时间空间复杂度都是 O(N)
var K int
var res int
func kthLargest(root *TreeNode, k int) int {
     K = k
     dfs(root)
     return res
}

func dfs(root *TreeNode) {
    if root == nil {
        return
    }
    dfs(root.Right)
    if K == 0 {
        return 
    }
    K--
    if K == 0 {
        res = root.Val 
    }
    dfs(root.Left)
}

0 赞同 0 条回复

神经蛙普通 2023年7月17日下午9:51

/**
    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {

    ArrayList<Integer> list = new ArrayList<Integer>();

    public int kthLargest(TreeNode root, int k) {
        recur(root);

        return list.get(list.size()  - k);
    }

    // 中序遍历
    public void recur(TreeNode node) {
        if (node == null) {
            return;
        }

        recur(node.left);
        list.add(node.val);
        recur(node.right);
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月17日下午9:30

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

    int cnt=0;
    int ans;
    public int kthLargest(TreeNode root, int k) {
        inOrder(root,k);
        return ans;
    }

    public void inOrder(TreeNode root,int k){
        if(root==null) return;
        inOrder(root.right,k);
        cnt++;
        if(cnt==k) {
            ans=root.val;
            return;
        }
        inOrder(root.left,k);
    }
}

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

0 赞同 0 条回复

ONE PIECE 普通 2023年7月17日下午8:21

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

    public void digui(TreeNode node){
        if(node == null) return;
        digui(node.right);
        k--;
        if(k==0) res = node;
        digui(node.left);
    }
}

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

0 赞同 0 条回复

阿尚普通 2023年7月17日下午7:43

//利用二叉搜索树中序遍历的特性
class Solution {
    int kMax;
    int rank;
    public int kthLargest(TreeNode root, int k) {
        travel(root, k);
        return kMax;
    }

    public void travel(TreeNode root, int k){
        if(root == null) return;

        travel(root.right, k);
        rank++;
        if(k == rank){
            kMax = root.val;
            return;
        }
        travel(root.left, k);
    }
}

0 赞同 0 条回复

V2ero 普通 2023年7月17日下午6:55

时间复杂度O(n)，空间复杂度O(n)

function kthLargest(root: TreeNode | null, k: number): number {
    const res = [];

    const dfs = (root: TreeNode | null) => {
        if(!root){
            return null
        }
        if(res.length > k){
            return
        }
        dfs(root.right);
        res.push(root.val);
        dfs(root.left);
    }

    dfs(root);

    return res[k - 1];
};

0 赞同 0 条回复

#00456B 普通 2023年7月17日下午6:41

思路

首先是BST，特性就是左子树和右子树的所有节点都分别小于或者大于root。所以为了得到递增的效果，需要用中序遍历的方法。

代码

class Solution {
public:
    vector<int> vec;
    int kthLargest(TreeNode* root, int k) {
        inorder(root);
        return vec[vec.size()-k];
    }
    void inorder(TreeNode* root){
        if(root == NULL){
            return ;
        }
        inorder(root->left);
        vec.push_back(root->val);
        inorder(root->right);
    }
};

改进

但是这样用了一个vector，然而除了第k大的数都用不上，所以为了降低空间复杂度，可以用一个参数来指定输出结果。
因为不能统计整个vector的数量，所以可以稍微改一下中序遍历的输出，改为右中左的顺序，这样的输出结果就是一个降序的过程，可以直接得到第k大的数。

class Solution {
public:
    int ans;
    int rank = 0;
    int kthLargest(TreeNode* root, int k) {
        inorder(root, k);
        return ans;
    }
    void inorder(TreeNode* root, int k){
        if(root == NULL){
            return ;
        }
        inorder(root->right, k);
        rank++;
        if(rank == k){
            ans = root->val;
            return ;
        }
        inorder(root->left, k);
    }
};

练习

把中序遍历用非递归的方法来一次。

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        return inorder(root, k);
    }
    int inorder(TreeNode* root, int k){
        stack<TreeNode*> stk;
        vector<int> vec;
        int ans;
        if(root == NULL){
            return ans;
        }
        TreeNode* cur = root;
        while(cur || !stk.empty()){
            if(cur){
                stk.push(cur);
                cur = cur->right;
            }
            else{
                cur = stk.top();
                stk.pop();
                vec.push_back(cur->val);
                cur = cur->left;
            }
        }
        for(int i = 0; i < k ; i++){
            ans = vec[i];
        }
        return ans;
    }
};

0 赞同 1 条回复

#00456B 普通 @ #00456B 2023年7月17日下午10:32

不用vector来辅助，直接用一个int来记录结果

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        return inorder(root, k);
    }
    int inorder(TreeNode* root, int k){
        stack<TreeNode*> stk;
        int ans;
        int rank = 0;
        if(root == NULL){
            return ans;
        }
        TreeNode* cur = root;
        while(cur || !stk.empty()){
            if(cur){
                stk.push(cur);
                cur = cur->right;
            }
            else{
                cur = stk.top();
                stk.pop();
                //开始中序过程
                rank++;
                if(rank == k){
                    ans = cur->val;
                    return ans;
                }
                cur = cur->left;
            }
        }
        return ans;
    }
};

Mooby 普通 2023年7月17日下午6:09

十
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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 || k 0) return;
dfs(root.right);
if (–k 0) res = root.val;
dfs(root.left);
}
}

0 赞同 0 条回复

艺普通 2023年7月17日下午5:30

“`c++
//二叉搜索树的中序遍历是递增的
class Solution {
public:
int count=0;
int kthLargest(TreeNode* root, int k) {
if (!root) return -1;
int r = kthLargest(root->right, k);
count++;
if (count == k) return root->val;
int l = kthLargest(root->left, k);
return l == -1 ? r : l;
}
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月17日下午1:05

7.17
Day10：下面是代码

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) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月17日下午12:26

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        vector<int> sort;
        stack<TreeNode*> stk;
        while(!stk.empty() || root!=nullptr){
            while(root!=nullptr){
                stk.push(root);
                root = root->right;
            }
            root = stk.top();
            stk.pop();
            sort.push_back(root->val);
            if(sort.size()==k){
                return sort[k-1];
            }
            root = root->left;
        }
        return -1;
    }
};

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

0 赞同 0 条回复

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

共以下 32 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

思路

代码

改进

练习

# 回答此问题取消回复

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

共以下 32 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

思路

代码

改进

练习

# 回答此问题 取消回复

# 回答此问题取消回复