【剑指Offer】54. 二叉查找树的第 K 个结点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
        private static int k1, res;

    public int kthLargest(TreeNode root, int k) {
        k1 = k;
        // 中序遍历（递增） 左根右
        dfs(root);
        return res;
    }

    private static void dfs(TreeNode root) {
        if(root == null || k1 == 0)
            return;
        // 第k大倒序
        // 右
        dfs(root.right);
        // 根
        if(--k1 == 0)
            res = root.val;
        // 左
        dfs(root.left);
    }
}

private TreeNode ret;
private int cnt = 0;

public TreeNode KthNode(TreeNode pRoot, int k) {
    inOrder(pRoot, k);
    return ret;
}

private void inOrder(TreeNode root, int k) {
    if (root == null || cnt >= k)
        return;
    inOrder(root.left, k);
    cnt++;
    if (cnt == k)
        ret = root;
    inOrder(root.right, k);
}