6
#yyds干货盘点# 解决剑指offer：二叉搜索树的第k个节点
source link: https://blog.51cto.com/u_15488507/5333247
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 解决剑指offer：二叉搜索树的第k个节点
原创1.题目：
给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。1.返回第k小的节点值即可2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-13.保证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的结点即可。
{5,3,7,2,4,6,8},3
2.代码实现：
import java.util.*;
public class Solution {
//记录返回的节点
private TreeNode res = null;
//记录中序遍历了多少个
private int count = 0;
public void midOrder(TreeNode root, int k){
//当遍历到节点为空或者超过k时，返回
if(root == null || count > k)
return;
midOrder(root.left, k);
count++;
//只记录第k个
if(count == k)
res = root;
midOrder(root.right, k);
}
public int KthNode (TreeNode proot, int k) {
midOrder(proot, k);
if(res != null)
return res.val;
//二叉树为空，或是找不到
else
return -1;
}
}
public class Solution {
//记录返回的节点
private TreeNode res = null;
//记录中序遍历了多少个
private int count = 0;
public void midOrder(TreeNode root, int k){
//当遍历到节点为空或者超过k时，返回
if(root == null || count > k)
return;
midOrder(root.left, k);
count++;
//只记录第k个
if(count == k)
res = root;
midOrder(root.right, k);
}
public int KthNode (TreeNode proot, int k) {
midOrder(proot, k);
if(res != null)
return res.val;
//二叉树为空，或是找不到
else
return -1;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK