此解为了更容易让大家理解，所以优化版本放在了最后
思路：对于二叉搜索树而言，中序遍历，就可以得到升序序列，拿到第k小不是秒杀吗？
public int KthNode (TreeNode root, int k) {
//对于二叉搜索树而言，中序遍历，就可以由小到大排出val值;
ArrayList<Integer> array = new ArrayList<>();
//得到顺序排列
InitArray(root, array);
//把不满足条件的排除
if(root == null || array.size() < k || k == 0){
return -1;
}
return array.get(k - 1);
}
//得到顺序排列
private void InitArray(TreeNode root, ArrayList<Integer> array){
if(root == null){
return;
}
InitArray(root.left, array);
array.add(root.val);
InitArray(root.right, array);
}优化：去掉了顺序表，减少了递归层次，但方法不变，依旧秒杀~
//记录递归次数
private int count = 0;
//记录第k小数字
private int ret = -1;
public int KthNode (TreeNode root, int k) {
fundMin(root, k);
if(ret != -1){
return ret;
}else{
return -1;
}
}
private void fundMin(TreeNode root, int k){
if(root == null || count > k){
return;
}
fundMin(root.left, k);
count++;
//遇到第k小就修改
if(count == k){
ret = root.val;
}
fundMin(root.right, k);
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124335.html
