思想: 以下是求BST的第k小结点： 根据BST的特性，所以可以这么干：先求左子树中结点的个数即为leftCount,然后讨论leftCount与k的大小关系，然后再到对应的子树中去找符合条件的结点 记root的左子树中结点的个数为leftCount if(leftCount< k-1) :去root的右子树中去找第k-leftCount大的结点 if(leftCount == k-1 ) 则root即为我们要找的结点 if(leftCount> k-1) ：去root的左子树中去找第k大结点 那么求第k大就应该反过来，要基于root的右子树中结点个数来反推： 记右子树中结点的个数为rightCount,则我们可以得知root为第rightCount+1大的结点(以根节点为第几大来推) if(rightCount+1==k) return root.val if(rightCount+1<k) 则去root左子树中第 k-(rightCount+1)大的结点 if(rightCount+1>k):则去root的右子树中找第k大的结点 【优化】：因为上面两者方法存在重复计算的问题(求k小时重复计算左子树中结点的个数，求k大时重复计算右子树中结点的个数) 所以，我们还可以利用BST的中序遍历序列是一个递增序列来求解 求第k小，直接使用中序遍历，当遍历到第K个结点时，该结点自然就是我们要找的第K小结点 求第k大，要翻转以下，要先去遍历右子树，再根，再左子树，此时还是一样，若遍历到第k个结点，则第k个结点即为我们所求的结点
时间复杂度O(n) , 空间复杂度O(n)
class Solution { int counts; public int kthLargest(TreeNode root, int k) { if(root==null)return Integer.MIN_VALUE; int leftRes = kthLargest(root.right,k); if(leftRes!=Integer.MIN_VALUE){ return leftRes; } if(++counts==k){ return root.val; } int rightRes = kthLargest(root.left,k); if(rightRes!=Integer.MIN_VALUE){ return rightRes; } return Integer.MIN_VALUE; } } } }