题目描述

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

难度简单148收藏分享切换为英文接收动态反馈

给定一棵二叉搜索树，请找出其中第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 ≤ 二叉搜索树元素个数

测试用例

• 功能测试（各种形态不同的二叉搜索树）
• 边界值测试（输入k为0、1、二叉搜索树的节点数、二叉树搜索树的节点数+1）
• 特殊输入测试（指向二叉搜索树根节点的指针为空指针）

题目考点

• 考察应聘者的只是迁移能力，利用中序遍历解题。
• 考察应聘者对二叉搜索树和中序遍历的特点的理解。

解题思路

按照中序遍历的顺序遍历一个二叉搜索树。

只要熟悉中序遍历的写法，那么这道题就不难了。

自己解题

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

参考解题

见自己解题。