algorithm - 我们可以构建一个只有后序遍历或前序遍历的完整二叉树吗？

例如，我们只提供后序遍历数组或只提供前序遍历数组。我们可以重建二叉树吗？如果我们知道二叉树是满的。此外，如果不是，如果同时知道前序和后序，是否可以构造完整的二进制文件？

最佳答案

不，您不能仅从一个列表中得出。

想想后序列表:4 5 2 3 1

    1         1
   / \       / \
  2   3     4   3
 / \           / \
4   5         5   2

两棵树都是可能的，但我们不知道哪一棵树生成了列表

假设树中的每个元素都是唯一的，我们知道 preorder 是这样构建的:

[Node][     LeftTree     ][     RightTree     ]

和这样的后序:

[     LeftTree     ][     RightTree     ][Node]

如果我们有两个列表，前序 1 2 4 5 3 和后序 4 5 2 3 1 ，我们知道 1 是树的根，因为它是前序列表的第一个数字(也是后序列表的最后一个数字)。此外，我们知道 2 必须是左树的根，3 必须是右树的根，因为它们是根节点之后的第一个数字，即左树或右树的根。考虑到这一点，我们可以将列表拆分为:

           [Root in preorder] [ LeftTree ] [RightTree] [Root in postorder]
preorder:        [1]             [2 4 5]      [3]
postorder:                       [4 5 2]      [3]              [1]

从这里你可以用左右树递归地执行这个算法，最后你得到这个:

    1
   / \
  2   3
 / \
4   5

由于每个元素都是唯一的，因此只有一种方法可以构建树，因此您可以从后序和前序列表重建树。

如果您有相同的元素，则无法构建唯一的树，例如:

preorder:  1 X X 5 X
postorder: X 5 X X 1

从这些列表中，您可以创建这两棵树:

    1         1
   / \       / \
  X   X     X   X
 / \           / \
X   5         5   X

关于algorithm - 我们可以构建一个只有后序遍历或前序遍历的完整二叉树吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23112589/