【剑指 Offer】54. 二叉搜索树的第k大节点(详细解析)

第 15 日：二叉搜索树的第k大节点

题目链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

题目

解题

1. 中序遍历的倒序

   解题思路：
   1.定义一个s遍历，保存当前是倒数第几位的数
   2.使用中序遍历的倒序，每遍历到一个结点s+1，直到s==k时返回该结点值，否则返回-1

   详细代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int s=0;
    public int kthLargest(TreeNode root, int k) {
        if(root==null) return -1;
        
        int r=kthLargest(root.right,k);
        
        s++;
        if(k==s) return root.val; 

        int l=kthLargest(root.left,k);

        return r>l?r:l;
    }
}
   
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26