题解 | #二叉搜索树的第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 proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    // 辅助函数：计算树的节点数
    public int count (TreeNode proot) {
        // write code here
        if (proot == null)
            return 0;
        return 1+count(proot.left)+count(proot.right);
    }
    // 判断左右子树的个数，然后决定传到左子树还是右子树中
    // 时间复杂度：O（n^2）空间复杂度：O（n）
    public int KthNode (TreeNode proot, int k) {
        // write code here
        if (proot == null || k < 1 || count(proot) < k)
            return -1;
        if (count(proot.left) == k-1)
            return proot.val;
        else if (count(proot.left) > k-1)
            return KthNode(proot.left, k);
        else
            return KthNode(proot.right, k-count(proot.left)-1);
    }
}