Преобразование обхода порядка уровней в обход обхода полного бинарного дерева
Учитывая порядок обхода уровня полного двоичного дерева в массиве, как сохранить обход по порядку упомянутого дерева в данном массиве, не создавая дерево.
Это то, что я придумал.
void recurse (int *inp, int size_array, int *output, int iter_a, int &iter_b)
{
if (iter_a>=size_array)
return;
recurse (inp,size_array,output,2*iter_a+1,iter_b);output[iter_b] = inp[iter_a];
iter_b++;recurse (inp,size_array,output,2*iter_a+2,iter_b);
}
Существует ли на месте нерекурсивное решение O (n) для указанной проблемы?
Решение
это функция, которую я создал для хранения обхода по порядку в массиве e из обхода по уровню или по порядку массива a, n — это длина массива a. Задайте начальные значения k = 0 и x = 0.
void convert(long long int a[],long long int e[],long long int n,long long int k,long long int x)
{
if((2*k+1)>=n||(2*k+2)>=n)
return;
convert(a,e,n,2*k+1,x);
e[x]=a[k];
x++;
convert(a,e,n,2*k+2,x);
return;
}
Другие решения
Это итеративное решение для преобразования порядка уровней в порядок, но не на место
private class Entry{
int data;
int pos;
Entry(int data, int pos){
this.data = data;
this.pos = pos;
}
}
public void convertLevelToInorder(int[] levelOrder){
// nodes are stored from index 1
int len = levelOrder.length;
int[] inOrder = new int[len];
Stack<Entry> stack = new Stack<Entry>();
int pos = 1;
int count = 1;
while(!stack.isEmpty() || pos < len){
while(pos < len && levelOrder[pos] != -1 ){
stack.push(new Entry(levelOrder[pos],pos));
pos = pos*2;
}
Entry e = stack.pop();
inOrder[count++] = e.data;
pos = e.pos*2+1;
}
for(int i=1;i<len;i++)
System.out.print(inOrder[i] + " ");
System.out.println();
}