给定一棵二叉搜索树,请找出其中的第k小的结点。
一开始我没有注意到二叉搜索树这个词,我还是以为是一个普通的二叉树,所以我就按照我的想法,将二叉树的节点放入到一个数组中。
由于一开始我没有注意到二叉搜索树这个概念,所以的我的思路是按照普通二叉树的查找进行的,具体思路如下所示:
moveArr
moveArr
函数中定义了将节点按照直接插入排序的思想进行排序。当我完成我的算法并且通过的时候,我再一次查看题解时发现,我还是粗心了,并没有发现题目中所给出的隐含的意思。二叉搜索树是一个非常特别的二叉树,当一个节点的左子树和右子树都存在时,左子树中的值都小于该节点,右子树中的所有值都大于该节点。
二叉搜索树的中序遍历就是一个升序排序的数组,所以查找第k小的节点,就查找数组中索引为k-1的节点即可。
但是中序遍历是找到所有的节点,但是我们只需要找到第k小的节点即可,所以我们对算法有了一些改进,使用非递归的中序遍历,找到第k小的节点就跳出循环。
具体的思路:
树节点的函数:
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot == null || k < 1) return null;
// 看到这个问题,我首先想到的方法是,将树放入到一个数组中,然后将数组进行判断,返现最小的数值
// 首先新建一个k位大小的数组,然后依次遍历二叉树,将数值插入到该数组中
TreeNode[] arr = new TreeNode[k];
addTreeNode(pRoot, arr);
return arr[k-1];
}
// 遍历将数节点加入到数组中
public void addTreeNode(TreeNode node, TreeNode[] arr){
if(node == null) return;
moveArr(node, arr);
if(node.left != null) addTreeNode(node.left, arr);
if(node.right != null) addTreeNode(node.right, arr);
}
// 数组移位, 判断数组要比哪一个小
public void moveArr(TreeNode node, TreeNode[] arr){
if(node == null) return;
for(int i=0; i<arr.length; i++){
if(arr[i] == null){
arr[i] = node;
return;
}else if(node.val < arr[i].val){
for(int j = arr.length-1; j > i; j--){
arr[j] = arr[j-1];
}
arr[i] = node;
return;
}
}
}
TreeNode KthNode(TreeNode pRoot, int k){
// 一开始没有仔细的看待问题,如果仔细的看问题以及对二叉树非常熟悉的话,应该第一时间就注意到了 二叉搜索树 这个词语
// ,二叉搜索树中一个节点的左子树中的值应该小于该节点,右子树中的值都应该大于该节点
if(pRoot == null || k < 1) return null;
// 二叉树的中序遍历就可以找到该节点的排序,只要找到第k个元素就可以找到问题中所要找的节点
// 非递归的方法需要使用Stack来存储父节点
TreeNode node = pRoot;
Stack<TreeNode> stack = new Stack<>();
int count = 0;
while(node != null || !stack.isEmpty()){
if(node != null){
stack.push(node);
node = node.left;
}else{
node = stack.pop();
count ++;
if(count == k) return node;
node = node.right;
}
}
return null;
}
原文:https://www.cnblogs.com/liulongtao/p/13951337.html