c++ - 将层序遍历转换为完全二叉树的中序遍历

Question

给定数组中一棵完整二叉树的层序遍历，如何在给定数组中存储所述树的中序遍历，而不构建树。这是我想出的。

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) 解决方案？

Answer 1

这是我创建的函数，用于将数组 a 的 levelorder 遍历中的中序遍历存储在数组 e 中，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;
}