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

迈不过友情╰ 2022-12-19 06:06 134阅读 0赞

# 题目 #

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:  
![在这里插入图片描述][20201105162840386.png_pic_center]

示例 2:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4OTg4OTY5_size_16_color_FFFFFF_t_70_pic_center]

限制：

*  1 ≤ k ≤ 二叉搜索树元素个数

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof][https_leetcode-cn.com_problems_er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof]

# 解题思路 #

二叉搜索树

*  左子节点的值 < 根节点的值
 *  右子节点的值 > 根节点的值
 *  中序遍历是一个递增序列

题目是要求第k大的节点

*  二叉搜索树的中序遍历为:左根右,是一个递增序列
 *  稍微变动一下:遍历顺序变为右根左,则得到一个递减序列
 *  遍历到第k个节点后,直接返回

# 代码 #

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        // 用来保存结果
        private int result;
        // 用来记录遍历到的数的个数
        private int index;
        public int kthLargest(TreeNode root, int k) { 
            index = k;
            dfs(root);
            return result;
        }
    
        private void dfs(TreeNode node) { 
            if (node == null) { 
                return;
            }
    
            // 中序遍历变种,右根左,降序排序
            dfs(node.right);
            index--;
            if (index == 0) { 
                result = node.val;
                return;
            }
            dfs(node.left);
        }
    }

# 复杂度 #

*  时间复杂度:O(n),极端情况下,数退化成链表,无论k的大小,占用O(n)时间复杂度
 *  空间复杂度:O(n),极端情况下,数退化成链表,递归占用空间为O(n)

[20201105162840386.png_pic_center]: /images/20221120/9a38c4f350ee47f1a6c11656b940cff0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4OTg4OTY5_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201105162909120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI4OTg4OTY5,size_16,color_FFFFFF,t_70#pic_center
[https_leetcode-cn.com_problems_er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof