考虑这样一种情况，您有两个节点列表，您所知道的只是一个节点表示某个树的预遍历遍历，另一个表示同一棵树的后序遍历。
我相信可以从这两个列表中完全重建树，并且我认为我有一种算法可以做到，但尚未证明。因为这将是一个硕士项目的一部分，所以我必须绝对确定这是可能且正确的（已通过数学证明）。但是，这不会成为项目的重点，因此我想知道是否可以使用该资源（例如纸质或书籍）作为证明。（也许在TAOCP中？有人知道该部分吗？）
简而言之，我需要一种在报价资源中经过验证的算法，该算法可以根据其前后顺序遍历来重建树。
注意：所讨论的树可能不会是二叉树，平衡树，也不会是任何容易的树。
注意2：仅使用预购或后购清单会更好，但是我认为这是不可能的。
注意3：一个节点可以有任意数量的子代。
注意4：我只关心兄弟姐妹的顺序。只有一个孩子时，左或右无关紧要。
您不能只使用一个列表，因为您将无法理解树的深度。因此，您肯定需要两个或多个列表。
这是我尝试的解决方案：
使用预遍历作为了解数据顺序的一种方法。这是有道理的，因为您知道第一个节点是顶部，并且知道遍历左侧的数据属于树的左侧，依此类推。
您的订单遍历可以确定树的深度。例如，假设我有一个这样的结构：
1 2 5 6 3 4 7 Where 2 is the parent of 3 and 4, and 5 is the parent of 7. Preorder: 1 2 3 4 5 7 6 Postorder: 3 4 2 7 5 6 1
我们知道我们从1开始，因为它是预遍历中的第一个节点。然后我们看下一个数字2，在后顺序中，因为数字2出现在节点1之前，所以我们知道2必须是1的子代。接下来看3。3出现在2之前，因此3是2的孩子。4在2之前但在3之后，因此我们知道4是2的孩子，但不是3的孩子。
现在，如果节点不是唯一的，则这可能不起作用，但至少是解决方案的开始。
编辑： 使用此解决方案可以保留子项的顺序，这仅是由于通过预顺序遍历了解节点的顺序，然后通过后顺序遍历了解结构。
我认为您需要购买该文档，但是…
以下是作为解决方案的书面证明：
http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa- cse/tutorials/tutorial09-solutions.pdf
