/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int kthVal = 0, count = 0;
    public int kthLargest(TreeNode root, int k) {
        // 递归中序遍历
        // 二叉搜索树的一个特性：通过中序遍历所得到的序列，就是有序的。
        traverse(root, k);
        return kthVal;
    }
    
    private void traverse(TreeNode root, int k) {
        // 二叉搜索树右子节点比根节点大，左子节点比根节点小
        // 注意是第K大，所以右->根->左；第K小才是左->根->右

        // 直接先遍历右子节点，因为右节点是最大的
        if (root.right != null) {
            traverse(root.right, k);
        }
        // 如果右子节点中没有满足k的值，那么最大值就是根节点
        // 因为count从0计数，k>=1，所以当count加1后的结果等于k时，那么该根节点的值就是第k大的值。
        // 注意：1.count++返回原来的值，++count返回加1后的值。
        //      2.count++不能作为左值，而++count可以
        if (++count == k) {
            kthVal = root.val;
            return;
        }
        // 走到这里说明递归了右节点仍未找到符合k的值，所以我们接着遍历左节点，直到找出符合k的值
        if (root.left != null) {
            traverse(root.left, k);
        }
    }
}