好的，假设我们有两个列表：二叉树的前序遍历值，以及列表中给出的中序遍历值。现在，我需要创建一棵树（以列表形式，例如 [1, [2, [2, None, None], None], [1, None, None]]）。我可以从遍历值中分辨出树的每一侧的根值和元素的数量，但我对如何创建树本身有点困惑。递归是解决这个问题的好主意吗，看看我们如何在主树中创建子树？
这也不能用类来完成。它必须是一个函数。课程会让事情变得更容易，但我不应该使用它们。
问问题
980 次
1 回答
0
这可能会有所帮助。
总结：
通过前序遍历[x1,...,xn]和中序遍历[z1,...,zn]，可以重建树如下：
根是前序遍历 x_1 的头部。令 k 为使 z_k=x1 的索引。那么[z_1,…,z_k−1]是左孩子的有序遍历，[z_k+1,…,z_n]是右孩子的有序遍历。按照元素个数，[x_2,…,x_k] 是左孩子的前序遍历，[x_k+1,…,x_n] 是右孩子的前序遍历。递归构建左右子树。
于 2014-03-09T00:07:06.403 回答