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

宁永久会员 2023年3月10日下午5:34

第一反应是中序遍历然后get（size – k）

class Solution {
    public int kthLargest(TreeNode root, int k) {
        //中序遍历就是按照顺序排列的，然后再geti  左中右
        //中序遍历，然后size - k
        //元素个数》=1
        //迭代实现
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list.get(list.size() - k);
    }
}
class Solution {
    public int kthLargest(TreeNode root, int k) {
        //递归实现
        List<Integer> list = new ArrayList<>();
        mid(root, list);
        return list.get(list.size() - k);
    }
    void mid(TreeNode root, List list){
        if(root == null){
            return;
        }
        mid(root.left, list);
        list.add(root.val);
        mid(root.right, list);
    }
}

然后发现可以简化代码，不需要遍历所有元素

class Solution {
    int k = 0;
    int res = 0;
    public int kthLargest(TreeNode root, int k) {
        //递归实现
        this.k = k;
        mid(root);
        return res;
    }
    void mid(TreeNode root){
        if(root == null || k <= 0){
            return;
        }
        mid(root.right);
        k--;
        if(k == 0){
            res = root.val;
            return;
        }
        mid(root.left); 
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月7日下午2:04

镜像中序遍历（右、根、左）非递归

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

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        int idx = 0;
        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.right;
            }
            TreeNode node = s.pop();
            if (++idx == k) return node.val;
            if (node.left != null) cur = node.left;
        }
        return -1;
    }
}

0 赞同 0 条回复

Gg 普通 2023年1月3日下午10:17

class Solution {
    public int kthLargest(TreeNode root, int k) {
        if(root == null || k == 0){
            return 0;
        }
        // 利用辅助栈，按右根左进行遍历
        Stack<TreeNode> stk = new Stack<>();
        TreeNode curr = root;
        int count = 0;
        while(curr != null || !stk.isEmpty()){
            if(curr != null){
                stk.push(curr);
                curr = curr.right;
            }else{
                curr = stk.pop();
                count ++;
                if(count == k){
                    return curr.val;
                }
                curr = curr.left;
            }
        }
        return 0;
    }
}

0 赞同 0 条回复

cute. 普通 2023年1月3日下午9:12

var kthLargest = function(root, k) {
    var stack = [];
    //  中序遍历:左 根 右 ，是一个有序的排列
    var inOrderTraverse = function(node) {
        if(node !== null){
           inOrderTraverse(node.left);
           stack.push(node.val);
           inOrderTraverse(node.right);
        }
    }
    inOrderTraverse(root);
    stack.reverse();
    return stack[--k];
};

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

0 赞同 0 条回复

PatNick 普通 2022年12月26日下午4:10

class Solution:
    def __init__(self):
        self.tree_list = []
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.printTree(root)
        return self.tree_list[k-1]
    # 将树上的节点按照从大到小打印
    def printTree(self,root):
        if root == None:
            return
        self.printTree(root.right)
        self.tree_list.append(root.val)
        self.printTree(root.left)

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:22

class Solution {
public:
    void dfs(TreeNode* root, int& k,int& res){ //使用回溯，后序遍历，从大到小搜索
        if(root==nullptr || k ==0) return;
        dfs(root->right,k,res);
        k--; //
        if(k==0) res = root->val;
        dfs(root->left,k,res);
    }

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

0 赞同 0 条回复

symbol 普通 2022年11月23日下午12:38

//二叉搜索树，中序遍历 右 根 左是递减的序列
func kthLargest(root *TreeNode, k int) int {
    var Help func(root *TreeNode) //声明递归函数
    var res int 

    Help = func(root *TreeNode){
        if root == nil{
            return
            }
        //右子树
        if root.Right != nil{
            Help(root.Right)
            }
        k --
        if k == 0{
        res = root.Val
            }
        //左子树
        if root.Left != nil{
            Help(root.Left)
            }
        }

    Help(root) //调用递归
    return res
}

0 赞同 0 条回复

xye 普通 2022年11月17日下午11:17

var target int
var n int

func kthLargest(root *TreeNode, k int) int {
    n = k
    right_root_left(root)
    return target
}

func right_root_left(root *TreeNode) {
    if root == nil || n <= 0 {
        return 
    }
    right_root_left(root.Right)
    n = n - 1
    if n == 0 {
        target = root.Val
    }
    right_root_left(root.Left)
}

时间O(n) 空间O(n)

0 赞同 0 条回复

浅夏的无奈普通 2022年11月13日上午12:19

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 条回复

一只骆驼普通 2022年11月9日下午7:19

用中序遍历特性

class Solution {
    List 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);
    }
}

优化一下
class Solution {
    int ans=0;
    int count=0;
    public int kthLargest(TreeNode root, int k) {
        nothing(root,k);
        return ans;
    }
    //反向中序遍历，从大往小走，第k个数的时候停止
    public void nothing(TreeNode root,int k){
        if(root.right!=null) nothing(root.right,k);
        if(++count==k){
            ans = root.val;
            return;
        }
        if(root.left!=null) nothing(root.left,k);
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月8日下午11:32

这个是来自leetcode jyd的代码，对python3还不太熟悉，不是很会使用类变量

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 条回复

小肸永久会员 2022年11月8日上午11:46

思路一：将二叉搜索树的中序遍历结果用一个链表存储起来，然后通过下标去第k大的元素。时间和空间复杂度都为O(N)。
思路二: 层序遍历二叉搜索树（访问顺序为右中左）的同时递减k并判断k是否等于0来返回结果。时间复杂度最坏情况下为O(N)，空间复杂度为O(N)。
思路三：稍微改变下中序遍历的顺序，为右中左，dfs实现，同时维护一个变量来判断是否为结果。这个变量为什么是类变量，而不是方法变量，方法变量的话递归时会有回溯操作，不好判断。时间复杂度最坏情况下为O(N)，空间复杂度O(N)。

class Solution {
    private int res = 0, k = 0;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    private void dfs(TreeNode root) {
        // k < 0 做剪枝处理
        if (root == null || k < 0) {
            return;
        }
        dfs(root.right);
        k --;
        if (k == 0) {
            res = root.val;
            return;
        }
        dfs(root.left);
    }
}

0 赞同 0 条回复

酥合普通 2022年11月7日下午10:33

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

    private List<Integer> inOrder = new ArrayList<>();

    public int kthLargest(TreeNode root, int k) {
        inOrderTree(root);
        return inOrder.get(inOrder.size() - k);
    }

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

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

0 赞同 0 条回复

@ 普通 2022年11月7日下午4:59

思路：按照右根左的顺序递归访问，期间维护变量i,直到++i k 就把当前val的值赋值给res
时间复杂度 O(N)
空间复杂度 O(N)

class Solution {
    int i = 0;
    int res = -1;

    public int kthLargest(TreeNode root, int k) {

        find(root, k);
        return res;

    }

    public void find(TreeNode head, int k) {
        if (head == null)
            return;

        find(head.right, k);

        if (i == k)
            return;

        if (++i == k)
            res = head.val;

        find(head.left, k);
    }
}

0 赞同 0 条回复

刺猬普通 2022年11月7日下午2:51

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        vector<int> v;
        inorder(root, v);
        return v.at(v.size() - k);
    }
    void inorder(TreeNode* root, vector<int> &v) {
        if(!root) return;
        inorder(root->left, v);
        v.push_back(root->val);
        inorder(root->right, v);
    }
};

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

0 赞同 0 条回复

马啸天永久会员 2022年11月7日下午12:53

    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 条回复

yanshuojune 普通 2022年11月6日下午5:19

解题思路：二叉搜索树具有左子树的值<根节点<右子树的值的特性，改进中序遍历，使用右->中->左的顺序递归，得到从大到小的排列顺序，取出第K-1个值即为第K大的节点。
时间复杂度：O(n)递归最大深度为N，链表
空间复杂度：O(n)

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

0 赞同 0 条回复

lobort 普通 2022年11月5日下午4:21

//利用二叉搜索数的性质来做  改变中序遍历的顺序 
class Solution {
    int count = 0;
    int res =0;

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

0 赞同 0 条回复

just 普通 2022年11月5日上午10:36

//一个小技巧就是按照RNL的顺序遍历bijiaozhiguan
/**
* 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 num;
int res;
bool fun(TreeNode root,int k){
if(!root) return false;
if(fun(root->right,k)) return true;
num++;
if(numk){
res=root->val;
return true;
}
if(fun(root->left,k)) return true;
return false;
}
int kthLargest(TreeNode* root, int k) {
num=0;
res=1;
fun(root,k);
return res;

};

0 赞同 0 条回复

你有点可爱喔普通 2022年11月3日下午7:02

解题思路：第k大，那么就是中序遍历，但是二叉搜索树中序遍历的结果是升序，求k大的将右子树、当前节点、左子树去做出这样的遍历。还有种方法，以中序遍历方式将其循环放入栈中，这样出栈顺序的结果就是从大到小
时间复杂度：O(n）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int count = 0;
    int num = 0;
    public int kthLargest(TreeNode root, int k) {
        //中序遍历
        this.count = k;
        right_mid_left(root);
        return num;
    }
    void right_mid_left(TreeNode root){
        if(root == null || count<0){
            return;
        }
        right_mid_left(root.right);
        count--;
        if(count == 0){
            num = root.val;
        }
        right_mid_left(root.left);
    }
}

0 赞同 0 条回复

优秀市民普通 2022年11月3日上午11:41

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        res = []
        def preOrder(root):
            if(not root):
                return 0
            res.append(root.val)
            left = preOrder(root.left)
            right = preOrder(root.right)
        preOrder(root)
        res.sort(reverse=True)        
        return res[k-1]

时间复杂度 on

0 赞同 0 条回复

y 普通 2022年11月2日下午11:18

var kthLargest = function(root, k) {
   let stack = [];
   const inorder = (root) => {
       if(root) {
           inorder(root.left);
           stack.push(root.val);
           inorder(root.right);
       }
   }
   inorder(root);
   return stack[stack.length - k]

};

中序遍历

0 赞同 0 条回复

Tolkien 永久会员 2022年11月2日下午9:00

/**
     * 递归 时间复杂度：O(n)，空间复杂度：O(n)
     */
    private LinkedList<Integer> result = new LinkedList<>();

    public int kthLargest(TreeNode root, int k) {
        List<Integer> ascSequence = inorder(root);
        return ascSequence.get(k-1);
    }

    private List<Integer> inorder(TreeNode node) {
        if (node == null) {
            return new LinkedList<>();
        }

        inorder(node.left);
        result.addFirst(node.val);
        inorder(node.right);

        return result;
    }
}

0 赞同 0 条回复

庄重普通 2022年11月2日下午1:34

//  思路:
//     1.对于搜索二叉树而言，中序遍历( 左 根 右 ) 的结果为一个顺序结构，从小至大排序
//     2.本题是第k大节点，可以 右 根 左 的顺序遍历
class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        m_k = k;
        right_root_left(root);

        return target;
    }

    void right_root_left(TreeNode* root){
        if(root == NULL || m_k < 0) return;
        right_root_left(root->right);
        if(m_k > 0){
            --m_k;
            target = root->val;
        }
        right_root_left(root->left);
        return;
    }

    int target;
    int m_k;
};
//时间复杂度O(n) 最差为O(n)
//空间复杂度O(n) 递归n次

0 赞同 0 条回复

是梦终空永久会员 2022年11月2日上午11:32

先遍历获取树的所有val，然后存入数组，排序后求倒数第k个元素。
打卡完才看到是二叉搜索树，有点写复杂了。定义一个全局a，右中左遍历，当a=0时候，就查找到了第k个大的数。
时间 O(n)
空间O(n)

class Solution {
    int count= 0;
    List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        f(root);
        int[] arr = new int[count];
        int j = count;
        count--;
        for(int i : list){
            arr[count--] = i;
        }
        int num = 0;
        Arrays.sort(arr);
        for(int i = 0;i<j-k;i++)    
            num++;
        return arr[num];
    }
    void f(TreeNode root){
        if(root == null)    return ;
        list.add(root.val);
        count++;
        f(root.left);
        f(root.right);
        return ;
    }
}

class Solution {
    int a = 0;
    int res = 0;
    public int kthLargest(TreeNode root, int k) {

        a = k;
        f(root);
        return res;
    }
    void f(TreeNode root){
        if(root == null || a<0) return ;

        if(root.right != null) f(root.right);
        a--;
        if(a == 0) res = root.val;
        f(root.left);
    }
}

0 赞同 0 条回复

追普通 2022年11月2日上午9:51

class Solution {
public:
    int res, k;
    int kthLargest(TreeNode* root, int k) {
        this->k = k;
        def(root);
        return res;
    }

    void def(TreeNode* root){
        if(root == nullptr) return;

        def(root->right);
        if(k == 0) return;
        if(--k == 0) res = root->val;
        def(root->left);
    }
};

二叉搜索树中序遍历的倒序就是从大到小排列的，因此使用中序遍历即可求解

0 赞同 0 条回复

派大星普通 2022年11月2日上午12:02

class Solution {
//中序遍历在集合中
//时间复杂度O(n)
//空间复杂度O(n)
     List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        if(root==null) {
            return 0;
        }
        middle(root);
        int value = list.get(list.size()-k);
        return value;
    }

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

0 赞同 0 条回复

天然普通 2022年11月1日下午10:31

用的遍历模版，先开始写的前序遍历，然后再sort，没有明白二叉搜索树的性质，中序就已经是有序的了时间复杂度O(n)，空间复杂度O(n)

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root: return None
        res,stark,num = [],[],root
        while num or stark:
            while num:
                stark.append(num)
                num = num.right
            tem = stark.pop()
            res.append(tem.val)
            num = tem.left

        return res[k-1]

0 赞同 0 条回复

Error 普通 2022年11月1日下午10:14

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

时间复杂度 O(n)

0 赞同 0 条回复

青木普通 2022年11月1日下午10:00

/**
    想了半天递归没写出来，先来个迭代，就是中序遍历换个方向，从左中右变成右中左
    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.right;
            }
            else{
                p = stack.pop();
                k-=1;
                if(k==0) return p.val;
                p = p.left;
            }
        }
        return -1;
    }
}


/**
    看了题解才明白递归，还是写的太少了
    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    int res, k;

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

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

0 赞同 0 条回复

So 普通 2022年11月1日下午9:46

/**
 * 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);
    }
}

时间：O(n)，空间：O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月1日下午9:11

按照中序遍历得到递增序列，使用list存储

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

class Solution {
    List 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);
    }
}

使用右根左，从大到小，利用count控制倒数的个数，及时截断

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

class Solution {
    int count;
    int ans;
    public int kthLargest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return ans;

    }
    public void inorder(TreeNode root){
        if(root.right != null) inorder(root.right);
        count--;
        if(count == 0){
            ans = root.val;
            return ;
        }
        if(root.left != null) inorder(root.left); 
    }
}

0 赞同 0 条回复

Whatever 永久会员 2022年11月1日下午8:42

利用搜索树中序遍历的特性，题目要求第k大，则从大到小遍历，先遍历右子树

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月1日下午7:20

时间复杂度为O（n），空间复杂度为O（lnn）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //找第k大的值，就用反中序遍历就好了
    int target = 0;
    int k = 0;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        f(root);
        return target;
    }
    void f(TreeNode root){
        //k<=0减少不必要的遍历
        if(root==null||k<=0) return;
        f(root.right);
        k--;
        if(k==0){
            target = root.val;
        }
        f(root.left);
    }
}

0 赞同 0 条回复

T 普通 2022年11月1日下午4:43

class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        rec(root);
        return res;
    }
    //中序遍历的逆序输出是递减序列
    public void rec(TreeNode root) {
        if(root == null || k == 0) return;
        rec(root.right);
        if(k == 1) res = root.val;
        k--;
        rec(root.left);

    }
}

0 赞同 0 条回复

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

共以下 35 个回答

镜像中序遍历（右、根、左）非递归

# 回答此问题取消回复

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

共以下 35 个回答

镜像 中序遍历（右、根、左） 非递归

# 回答此问题 取消回复

镜像中序遍历（右、根、左）非递归

# 回答此问题取消回复