题解 | #第k轻的牛牛#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    public int kthLighest (TreeNode root, int k) {
        kth(root,k);
        return res;
    }
    int count = 0;
    int res = 0;
    void kth(TreeNode root,int k){
        if(root == null) return;
        kth(root.left,k);
	  //当count== k时root.val表示的就是第k小的数
        count++;
        if(count == k) res = root.val;
        kth(root.right,k);
    }
}

相似题型：https://www.nowcoder.com/practice/8e5f73fa3f1a407eb7d0b0d7a105805e?tpId=354&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D354

我们看此题是一棵二叉搜索树，二叉搜索树的中序遍历就是按顺序读的，那么我们可以通过中序遍历来遍历出第k大/小的数。