二叉搜索树（二叉排序树）的第k小节点

概念与分析

首先明确一个概念，二叉搜索树/二叉排序树的特点是：

• 二叉树的任意节点T,都满足T.left.val < T.val && T.right.val > T.val

那么通过这一特点就有一个性质：二叉排序树/二叉搜索树 的 中序遍历 结果是递增序列

那么最简单的方法就是将树遍历一遍，然后存到数组A中，返回A[k-1]即可。

这种方法的时间效率，空间效率都是O(N) (其中N表示树中有多少个节点，且不考虑递归所带来的空间消耗)

那么我们可不可以考虑在递归的过程中保存一个计数器，当计数器值为k时，即为找到？
答案是可以的，我们要仔细思考清楚。

代码实现

int index = 0; //计数器
TreeNode KthNode(TreeNode root, int k) {

   if(root == null){
       return null;
   }
   //中序遍历寻找第k个
   TreeNode node = KthNode(root.left,k);
   if(node != null) {
       return node;
   }
   index ++;
   if(index == k) {
       return root;
   }
   return KthNode(root.right,k);
}

定义函数KthNode为TreeNode KthNode(TreeNode root, int k)，表示以root为根的二叉搜索树中，查找到第k小的节点，如果存在则返回此节点，不存在则返回NULL。

那么我们的思路就是：

1. 先找root左子树，看是否存在第k小的节点，如果存在，那么直接返回左子树的第k小节点即可。否则进入第2步
2. 如果左子树不存在第k小的节点，那么我们就看root节点是否就是第k个节点，如果是，则返回。否则进入第3部
3. 直接求右子树是否存在第k小的节点

那么计数器怎么计数的呢？这个是关键！！

我们可以先考虑少量数据的情况。对于只含有3个节点的树，应该是每当遍历一个节点后，计数器就加1。如下图所示：先序遍历到2，进入步骤1，找左子树，发现左子树为空，直接返回NULL；那么进入第2步，判断当前节点是否是第k个节点，显然当前节点是第一个节点，所以在第1，2步骤之间我们需要将计数器+1，然后第2步判断2是否为第k个节点，如此下去，如上面所列的代码一样。

      1
   ↙   ↘
  2       3

更多

总结：主要是理解递归的流程，计数器到底该怎么变化，在何时变化，以及递归的流程安排。

上面我们提到的是求第k小的节点，那么当我们求第k大的节点时，该怎么做呢？同样，我们可以按找这样的方式遍历二叉搜索树：先遍历又子树，再遍历当前节点，再遍历左子树；这样得到的结果为一个递减的序列，那么现在的问题就是找到这个序列的第K个元素，问题与上面一样了，代码实现只需稍作修改即可。