AlgoPressAppearance
54-二叉搜索树的第k大节点
题目描述
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/ 给定一棵二叉搜索树，请找出其中第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 大的值， 从大到小 遍历顺序应该是 : 右根左 最简单的方法，就是遍历，增加到数组中去，最后取出第k个元素，此方法需要开辟一个新的空间 另外的方法是 设置外部变量累加器 count ，当 count == k 的时候，该元素即为 第 k 大的元素
实现代码
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int count = 0;
int answer = 0;
private void dfs(TreeNode cur, int k){
// 右根左
if(cur.right != null){
dfs(cur.right, k);
}
count++;
if(count == k){
answer = cur.val;
return;
}
if(cur.left != null){
dfs(cur.left, k);
}
}
public int KthLargest(TreeNode root, int k) {
if(root == null){
return -1;
}
dfs(root,k);
return answer;
}
}
实现代码2
csharp
public class Solution {
int count = 0;
int answer = 0;
private void dfs(TreeNode cur, int k){
if(cur == null){
return;
}
dfs(cur.right);
count++;
if(count == k){
answer = cur.val;
return;
}
dfs(cur.left);
}
public int KthLargest(TreeNode root, int k) {
if(root == null){
return -1;
}
dfs(root,k);
return answer;
}
}