如果有一个完全二叉树的层序遍历数组,如何将该树的中序遍历存储在给定的数组中,而不需要构建整棵树。以下是我的想法。
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)原地解决方案来解决这个问题?