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

Dear 丶 2023-02-18 12:54 2阅读 0赞

# 题目： #

[面试题54. 二叉搜索树的第k大节点][54. _k]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

![在这里插入图片描述][20200617213944643.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

# 代码： #

/** * 面试题54 */
    public class 面试题54 { 
    
        public int ans = 0;
        public int count = 0;
    
        public int kthLargest(TreeNode root, int k) 
        { 
            dfs(root, k);
            return ans;
        }
    
        public void dfs(TreeNode root, int k)
        { 
            if(root == null) // 当节点 root 为空（越过叶节点），则直接返回；
            { 
                return;
            }
            if(count == k) // 若 count == k ，代表已找到目标节点，无需继续遍历，因此直接返回；
            { 
                return;
            }
            dfs(root.right, k); // 递归右子树
            count++; // 执行 count++（即 count 从 0 加至 k）；
            if(count == k) // 若 count == k ，代表当前节点为第 k 大的节点，因此记录 ans = root.val；
            { 
                ans = root.val;
                return; // 这里的 return 可以避免之后的无效迭代 dfs(root.left, k)；
            }
            dfs(root.left, k); // 递归左子树
        }
    
        public static void main(String[] args) { 
            Integer nums[] = {  5, 3, 6, 2, 4, null, null, 1 };
            TreeNode root = ConstructTree.constructTree(nums);
            TreeOperation.show(root);
            System.out.println("***************************************");
            int k = 3;
            面试题54 test = new 面试题54();
            int res = test.kthLargest(root, k);
            System.out.println(res);
        }
    }

# 参考： #

1.  [面试题54. 二叉搜索树的第 k 大节点（中序遍历 + 提前返回，清晰图解）][54. _ k _ _]

[54. _k]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617213232367.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[20200617213944643.png]: https://img-blog.csdnimg.cn/20200617213944643.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200617213508152.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200617213523159.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200617213608974.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200617213645458.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[54. _ k _ _]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solution/mian-shi-ti-54-er-cha-sou-suo-shu-de-di-k-da-jie-d/