解决方案

方法一：递归

思路

前序遍历为：

• (root node) (preorder of left branch) (preorder of right branch)

而后序遍历为：

• (postorder of left branch) (postorder of right branch) (root node)

例如，如果最终的二叉树可以被序列化的表述为 [1, 2, 3, 4, 5, 6, 7]，那么其前序遍历为 [1] + [2, 4, 5] + [3, 6, 7]，而后序遍历为 [4, 5, 2] + [6, 7, 3] + [1].

如果我们知道左分支有多少个结点，我们就可以对这些数组进行分组，并用递归生成树的每个分支。

算法

我们令左分支有 $$L$$ 个节点。我们知道左分支的头节点为 pre[1]，但它也出现在左分支的后序表示的最后。所以 pre[1] = post[L-1]（因为结点的值具有唯一性），因此 L = post.indexOf(pre[1]) + 1。

现在在我们的递归步骤中，左分支由 pre[1 : L+1] 和 post[0 : L] 重新分支，而右分支将由 pre[L+1 : N] 和 post[L : N-1] 重新分支。

复杂度分析

• 时间复杂度： $$O(N^2)$$ ，其中 $$N$$ 是结点的数量。
• 空间复杂度： $$O(N^2)$$ 。
  
  

方法二：递归（节约空间的变体）

说明

我们这里提出一个方法一的变体，使用索引指代子数组 pre 和 post，而不是通过那些子数组的副本。这里，(i0, i1, N) 指的是 pre[i0:i0+N], post[i1:i1+N].

复杂度分析

• 时间复杂度： $$O(N^2)$$ ，其中 $$N$$ 是结点的数目。

• 空间复杂度： $$O(N)$$ ，答案所用去的空间。