题解 | #第k轻的牛牛#

知识点

树，中序遍历

解题思路

根据二叉搜索树的性质，当前节点的排名与其位置有关，

如果是左叶子节点等于前置排名+1，如果是中间节点等于前置排名+左子树节点数量+1，如果是右叶子节点等于父节点排名+1。

因此我们要使用中序遍历。

例如这棵树，初始前置排名0，根节点9，左子树不为空找到5，左子树不为空找到4，4的前置排名为0，所以4的排名为1，5的排名等于前置排名0+左子树数1+1=2，5的右子树不为空，找到7，7的左子树不为空，6的排名为前置排名2+1=3，依次类推。

Java题解

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整型
     */
   Map<Integer,Integer> map = new HashMap<>();
    public int kthLighest (TreeNode root, int k) {
        // write code here
        getOrder(root,0);
        return map.get(k);
    }

    /**
    * preNum:前置节点的排名
     */
    public int getOrder(TreeNode root, int preNum){
        int num = 1;  //节点数量
        if(root.left != null){
            num += getOrder(root.left,preNum);
        }
        map.put(num + preNum,root.val);
        if(root.right != null){
            num += getOrder(root.right,preNum + num);
        }
        return num;
    }
}