题目：
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
限制：
1 ≤ k ≤ 二叉搜索树元素个数
分析：
二叉搜索树的特点就是根左<根<根右，所以我们经过思考可知，通过中序遍历（左中右），得到的是二叉搜索树值的升序。
因为我们要得到第K大的结点值，所以我们要值的降序排列，那么我们就用逆中序遍历（右中左），根据k值来记录当前是第几个结点。
代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int count,res; public int kthLargest(TreeNode root, int k) { this.count = k; method(root); return res; } public void method(TreeNode root) { if(root==null) return; if(count == 0) return; method(root.right); count--; if(count==0) { res = root.val; } method(root.left); } }
因为进入递归之后记录数据k很乱，所以我们定义两个类变量count（用来记录当前是第几个结点）和res（用来存储第K大的值）。
思考：
之前我总是想不通为什么method(root.right);调用后要count-- 表示这个结点已经被遍历。
那method(root.left); 后面为什么不count-- 呢？
后来我想通了，我能提出这个问题说明我没懂递归的真谛。这个count--不是method(root.right);的count--。而是root的count-- 说明root这个结点被遍历到了。
递归整体可以这么理解，你就想先遍历一个结点（不带递归）
public void method(TreeNode root) { if(root==null) return; if(count == 0) return; count--; if(count==0) { res = root.val; } }
当我把递归删掉后，我的目的就是遍历一个结点。
但是当我有遍历需求后，我想先看右边的，再遍历左边的。那么我就直接上下加个递归。
即：
public void method(TreeNode root) { if(root==null) return; if(count == 0) return; method(root.right); count--; if(count==0) { res = root.val; } method(root.left); }
你可以将复杂的逻辑改成打印一个结点，那么我想先打印左再中再右。那么就上下加递归函数就可以了。
void method(TreeNode root) { if(root == null) return; method(root.left); //左 System.out.println(root.val); //打印 method(root.right); //右 }
就是这样。
