LeetCode[剑指Offer54]二叉搜索树的第K大节点

难度：简单

题目：

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

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

---

 示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

---

限制：

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

Related Topics

• 树
• 深度优先搜索
• 二叉搜索树
• 二叉树

---

重点！！！解题思路

第一步：

此题我们首先采用递归和栈的思想来解决

根据此题例子可知，所有比根节点大的节点都在右子树，比根节点小的节点都在左子树

如果想求第k大个节点，一定是从右子树中找起

第二步：

判断，当k大于右子树节点总和时，那么k肯定在左子树中

如果k=右子树节点总和+1时，那么k是根节点

如果k小于右子树节点总和时，那么k肯定在右子树中

已知上述结论，此题易解

源码：

class Solution {
    public int kthLargest(TreeNode root, int k) {
        int cnt=getCount(root.right);  //得到右子树的所有节点
        if (cnt>=k) return kthLargest(root.right,k);  //以下开始递归求解
        if (cnt+1==k) return root.val;
        return kthLargest(root.left,k-cnt-1);
    }
    public int getCount(TreeNode root) {
        if (root==null) return 0;
        return 1+getCount(root.left)+getCount(root.right);
    }
}

运行结果：

 

如果您还有什么疑问或解答有问题，可在下方评论，我会及时回复。 

系列持续更新中，点个订阅吧