剑指Offer系列（java版，详细解析）54.二叉搜索树的第K大的节点
题目描述
剑指 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);
}
}
参考解题
见自己解题。