如何根据给定的遍历构建二叉树？

Question

好吧，假设我们有两个列表：一个是二叉树的前序遍历值，另一个是中序遍历值。现在，我需要创建一棵树（用列表的形式，比如说 [1, [2, [2, None, None], None], [1, None, None]]）。通过遍历值，我可以知道树的根节点值和树的左右两边各有多少个元素，但我有点搞不清楚怎么实际构建这棵树。考虑到我们是在主树中创建子树，使用递归来解决这个问题是不是个好主意呢？

而且，这个过程不能用类来实现，只能用函数。虽然用类会简单很多，但我不能使用它们。

Answer 1

这段内容可能会对你有帮助。

总结一下：
如果你有一个前序遍历的结果 [x1,…,xn] 和一个中序遍历的结果 [z1,…,zn]，你可以按照下面的方法重建这棵树：

树的根节点就是前序遍历中的第一个元素 x1。
接下来，找到中序遍历中与 x1 相等的元素的索引，记作 k。这样，[z1,…,zk−1] 就是左子树的中序遍历，而 [zk+1,…,zn] 就是右子树的中序遍历。
根据元素的数量，[x2,…,xk] 就是左子树的前序遍历，而 [xk+1,…,xn] 就是右子树的前序遍历。然后，继续递归地构建左子树和右子树。