使用其前序遍历及其镜像树的前序遍历构建满二叉树

我们需要创建一个软件来表示这两个前序遍历，以便根据一个满二叉树及其镜像树的前序遍历的两个数组来构建二叉树。

满二叉树是一种二叉树，其中每个节点都有零个或两个子节点。

需要注意的是，这两个遍历不能用来构建一个通用的二叉树。但是，我们可以轻松地利用上述遍历来构建一个满二叉树。

示例

方法 1：取两个给定的数组，preOrder[] = 1, 2, 5, 6, 4, 7, 8 和 preOrderMirror[] = 1,4,8,7,2,6,5

树的根是 preOrder[] 和 preOrderMirror[] 中最左边的元素。数组大小大于一且树是满的。根的左子节点必须是 preOrder 中紧跟在 1 后面的值，而根的右子节点必须是 preOrderMirror 中紧跟在 1 后面的值。

在这种情况下，1 代表根，2 代表左子节点，4 代表右子节点。

如何找到左子树中的所有节点？

我们知道 2 是左子树中所有节点的根，4 是右子树中所有节点的根。preOrderMirror 需要将 2 的所有节点放在根节点 1 的左子树中，将 4 及 2 之前的节点放在根节点 1 的右子树中。现在我们知道根是 1，左子树的元素是 2, 6, 5，右子树的元素是 4, 8, 7。

我们将递归地使用上述策略来生成以下树

上述技术实现如下

C++ 程序

输出

5 2 6 1 7 4 8

这里，我们可以看到时间复杂度将是O(n²)

并且，辅助空间也将是O(n)。

方法 2：如果我们仔细观察，我们可以注意到原始树的后序遍历是镜像树的前序遍历的逆序。与上面类似，我们也可以从给定的前序和后序遍历构建树。