二叉搜索树的第k个节点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

分析

根据二叉搜索树的特性：左子树小于根节点，右子树大于根节点。那么对于给定的二叉搜索树，进行中序遍历即得出是顺序列数，计数找出第k位即可。

实现

int count = 0;
TreeNode KthNode(TreeNode root, int k){
      if(root != null){
          TreeNode node = KthNode(root.left,k);
          if(node != null){
              return node;
          }
          count++;
          if(count == k){
              return root;
          }
          node = KthNode(root.right,k);
          if(node != null)
             return node;
      }
      return null;
}