LeetCode 二叉搜索樹的第k大節(jié)點 [簡單]
給定一棵二叉搜索樹钓觉，請找出其中第k大的節(jié)點
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
示例 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 ≤ 二叉搜索樹元素個數(shù)
題目分析
解法1
搜索二叉樹，中序遍歷為正序捆交，因為需要尋找的是第k大的，也就是中序倒序的第k個吆你，中序倒序的遍歷為 右 中 左
代碼實現(xiàn)
public class KthLargest {
private static int res, k;
public int kthLargest(TreeNode root, int k) {
KthLargest.k = k;
dfs(root);
return res;
}
private static void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (k == 0) {
return;
}
if (--k == 0) {
res = root.val;
}
dfs(root.left);
}
}
