我正在解决HackerEarth问题之一 . 问题陈述如下,
给定一个包含N个节点的完整二叉树,并且每个节点都附加一个不同的整数 ai ,找到可以将二进制树转换为二叉树搜索树的最小交换次数 . 在一次交换中,您可以选择任意两个节点并交换它们的值 .
您将获得二叉树的数组表示 . 树的根将在 a[1] 根的左子将在 a[2] ,root的右子将在a3 . 数组位置 k 处的节点的左子节点将位于 a[2∗k] 处,并且阵列位置k处的节点的右子节点将位于 a[2∗k+1] 处 .
问题是如何将给定数组转换为树的有序数组 . 我尝试了下面的代码 . 在网上我没有找到任何链接 .
static void inOrderArr(int destIndex,int index, int[] source, int[] dest) {
int leftIndex = (index ) * 2;
int rightIndex = (((index ) * 2) + 1);
if(leftIndex<source.length){
inOrderArr(destIndex,leftIndex, source,dest);
}
System.out.println(index);
dest[destIndex++] = source[index-1];
if(rightIndex<source.length){
inOrderArr(destIndex,rightIndex, source,dest);
}
}
2 回答
我尝试了以下解决方案,它的工作原理 .
这是Node类型声明
试试这个!
我们的想法是使用二进制搜索树的顺序遍历按其值的递增顺序这一事实 . 因此,找到二进制树的inorder遍历并将其存储在数组中并尝试对数组进行排序 .
下面是c中的代码,用于将给定数组转换为树的有序数组 .