面试题54. 二叉搜索树的第k大节点

快来打我* 2023-02-18 04:30 30阅读 0赞

# 题目来源 #

[leetcode][]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 中序遍历 ##

### GO ###

func kthLargest(root *TreeNode, k int) int {
        
        ans := helper(root)
        if len(ans) >= k{
        
            return ans[k - 1]
        }
        return 0
    }
    
    func helper(root * TreeNode) []int {
        
        var ans []int
        if root != nil {
        
            ans = append(ans, helper(root.Right)...)
            ans = append(ans, root.Val)
            ans = append(ans, helper(root.Left)...)
        }
        return ans
    }

### JAVA ###

中序遍历二叉搜索树，遍历的同时，把遍历到的节点存到一个可变数组里

public int kthLargest(TreeNode root, int k) {
        
            List<Integer> list = new ArrayList<>();
            helper(root, list);
            return list.get(list.size() - k);
        }
    
        private void helper(TreeNode root, List<Integer> list){
        
            if (root == null){
        
                return;
            }
    
            helper(root.left, list);
            list.add(root.val);
            helper(root.right, list);
        }

![在这里插入图片描述][20200616095244200.png]

*  优化：

class Solution {
        
    
        public int kthLargest(TreeNode root, int k) {
        
            List<Integer> list = new ArrayList<>();
            helper(root, list);
            return list.get(list.size() - k);
        }
    
        private void helper(TreeNode root, List<Integer> list){
        
            if (root == null){
        
                return;
            }
    
            if (root.left != null){
        
                helper(root.left, list);
            }
            
            list.add(root.val);
            if (root.right != null){
        
                helper(root.right, list);
            }
        }  
    }

![在这里插入图片描述][20200616095347197.png]  
当遍历到了第K大数的时候，就可以停止遍历了  
【注意是第K大，所以右根左；第K小才是左根右】

class Solution {
        
    
        private int ans, cnt;
        public int kthLargest(TreeNode root, int k) {
        
            helper(root, k);
            return ans;
        }
    
        private void helper(TreeNode root, int k){
        
            if (root == null){
        
                return;
            }
    
    
             helper(root.right, k);
            if (++cnt == k){
        
                ans = root.val;
                return;
            }
            helper(root.left, k);
        }
    }

![在这里插入图片描述][2020061610002953.png]

将上面改写成栈

public int kthLargest(TreeNode root, int k) {
        
            int ans = 0, cur = 0;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
    
    
            while (!stack.empty()){
        
                TreeNode peek = stack.pop();
                if (peek != null){
        
                    if (peek.left != null){
        
                        stack.push(peek.left);
                    }
                    stack.push(peek);
                    stack.push(null);
                    if (peek.right != null){
        
                        stack.push(peek.right);
                    }
                }else{
        
                    TreeNode tmp = stack.pop();
                    if (++cur == k){
        
                        return tmp.val;
                    }
                }
            }
    
            return ans;
        }

![在这里插入图片描述][20200616101733671.png]

[leetcode]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020061610182635.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200616095244200.png]: https://img-blog.csdnimg.cn/20200616095244200.png
[20200616095347197.png]: https://img-blog.csdnimg.cn/20200616095347197.png
[2020061610002953.png]: https://img-blog.csdnimg.cn/2020061610002953.png
[20200616101733671.png]: https://img-blog.csdnimg.cn/20200616101733671.png