108 二叉搜索树中的第k小的元素

问题描述：给定一个二叉搜索树的根节点root，和一个整数k，请你设计一个算法查找其中第k个最小元素(从1开始计数)

中序遍历求解：对于二叉搜索树的中序遍历是有序的，从而使用一个全局变量记录是第几次调用该dfs函数，当地k次调用时返回其值。

int kSmall=0;
int kSmallNumber=0;
public void findKSmall(TreeNode root,int k)
{
if(root==null){return;}
findKSmall(root.left);
kSmall++;
if(kSmall==k){kSmallNumber=root.val;return;}
findKSmall(root.right);
}
public FindKSmall(TreeNode root,int k)
{
findKSmall(root,k);
???????return?kSmall;
}

统计节点个数：首先由于二叉搜索树的特性，左侧节点一定比根节点小，右侧节点一定比根节点大，从而可以先搜索左子树，若左子树的个数小于k，所寻找的节点一定在根节点或右侧节点，则在右侧节点进行寻找。
?

int counNodes(TreeNode root)
{
if(root==null){return 0;}
return 1+countNodes(root.left)+countNodes(root.right);
}
int kSmallNumber=0;

public void findKSmall(TreeNode root,int k)
{
int left=countNodes(root.left)
if(left<k-1)
{
findKSmall(root.right,k-left-1);
}else if(left+1==k)
{
kSmallNumber=root.val;
}else
{
findKSmall(root.left);
}
}
public int FindKSmall(TreeNode root,int k)
{
findKSmall(root,k);
???????return?kSmallNumber;
}