二叉搜索树的第k个结点(剑指offer第63题)
程序员文章站
2022-07-10 20:14:42
...
一、题目描述
给定一棵二叉搜索树,请找出其中的第k小的结点。
例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
二、解题思路
思路:搜索二叉树采用中序遍历的结果就是排好序的,我们用list保存下遍历的结果,在找到第k个值。
改进思路:不用list保存,使用一个变量作为计数器,累加到k值时,返回(递归遍历)
三、java代码
public class Solution_63 {
/**
* 给定一棵二叉搜索树,请找出其中的第k小的结点。
* 例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
*/
ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
TreeNode KthNode_1(TreeNode pRoot, int k)
{
//搜索二叉树采用中序遍历的结果就是排好序的,我们用list保存下遍历的结果,在找到第k个值。
if(pRoot == null || k<=0){
return null;
}
inOrder(pRoot);
TreeNode treeNode = pRoot;
if(k<=arr.size()){
treeNode = arr.get(k-1);
}else {
return null;
}
return treeNode;
}
public void inOrder(TreeNode root){ //中序遍历
if(root == null){
return;
}
if(root.left != null){
inOrder(root.left);
}
arr.add(root);
if(root.right != null){
inOrder(root.right);
}
}
//改进:不用list保存,使用一个变量作为计数器,累加到k值时,返回(递归遍历)
int index = 0; //计数器
TreeNode KthNode_2(TreeNode pRoot, int k){
if(pRoot != null){
TreeNode node = KthNode_2(pRoot.left, k);
if(node != null){
return node;
}
index ++;
if(index == k){
return pRoot;
}
node = KthNode_2(pRoot.right, k);
if(node != null){
return node;
}
}
return null;
}
//也是改进版,非递归遍历,用循环
int count = 0; //计数器
TreeNode KthNode_3(TreeNode pRoot, int k)
{
if(count > k || pRoot == null)
return null;
TreeNode p = pRoot;
Stack<TreeNode> LDRStack = new Stack<TreeNode>();
TreeNode kthNode = null;
while(p != null || !LDRStack.isEmpty()){
while(p != null){
LDRStack.push(p);
p = p.left;
}
TreeNode node = LDRStack.pop();
System.out.print(node.val+",");
count++;
if(count == k){
kthNode = node;
break;
}
p = node.right;
}
return kthNode;
}
}