categories: [Blog,Algorithm]

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

难度简单122
给定一棵二叉搜索树，请找出其中第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. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  12.     int res, k;
  13.     public int kthLargest(TreeNode root, int k) {
  14.         this.k = k;
  15.         dfs(root);
  16.         return res;
  17.     }
  18.     void dfs(TreeNode root) {
  19.         if(root == null) return;
  20.         dfs(root.right);
  21.         if(k == 0) return;
  22.         if(--k == 0) res = root.val;
  23.         dfs(root.left);
  24.     }
  25. }
  27. // 作者：jyd
  28. // 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solution/mian-shi-ti-54-er-cha-sou-suo-shu-de-di-k-da-jie-d/

中序遍历倒序