描述
给定一棵结点数为 n 二叉搜索树，请找出其中的第 k 小的TreeNode结点。
数据范围： 0 \le n <= 1000≤n<=100，0\le k \le 1000≤k≤100，树上每个结点的值满足 0 \le val \le 100 0≤val≤100
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
注意：不是返回结点的值
如输入{5,3,7,2,4,6,8},3时，二叉树{5,3,7,2,4,6,8}如下图所示：
该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第3个结点的结点值为4，故返回对应结点值为4的结点即可。
输入描述：
提示：当n为0或者k为0时返回空。
示例1
输入：
{5,3,7,2,4,6,8},3
返回值：
4
说明：
按结点数值升序顺序可知第三小结点的值为4 ，故返回对应结点值为4的结点即可。
示例2
输入：
{},1
返回值：
“null”
说明：
结点数n为0，所以返回对应编程语言的空结点即可。
结题思路：
1.对树进行中序遍历，即先访问左孩点，然后访问根节点，最后访问右孩子。用一个ArrayList保存各个节点，ArrayList.get(k-1)即为第k小的数。代码如下：
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.ArrayList;
public class Solution {
ArrayList<TreeNode> cap = new ArrayList<>();
TreeNode KthNode(TreeNode pRoot, int k) {
if(k <= 0) return null;
helper(pRoot);
return k <= cap.size() ? cap.get(k-1) : null;
}
void helper(TreeNode node){
if(node == null) return;
helper(node.left);
cap.add(node);
helper(node.right);
}
}
2.优化
其实只要遍历中序遍历的前k个节点即可，k+1后面的可以不进行遍历。因此，同样的遍历思路，增加一个计数器index记录已排序的数量。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.ArrayList;
public class Solution {
int index = 0;
TreeNode KthNode(TreeNode pRoot, int k) {
//2.优化后增加一个计数器index,省去list
if(pRoot == null) return null;
TreeNode node = KthNode(pRoot.left, k);
if(node != null) return node;
index ++;
if(index == k) return pRoot;
return KthNode(pRoot.right, k);
}
}