我们能否只使用后序遍历或前序遍历构建一棵完整的二叉树？

Question

例如，我们只提供后序遍历数组或者先序遍历数组。我们能否重构二叉树？如果我们知道该二叉树是满二叉树，那么是否能够构建出来？此外，如果不是满二叉树，同时知道先序遍历和后序遍历，是否有可能构建出完整的二叉树？

- Makara

---

“如果二叉树是满的”是什么意思？你是指平衡吗？ - Absurd-Mind

根据Wikipedia的解释，“满二叉树是一棵除了叶子节点外，每个节点都有两个子节点的树。” - Bernhard Barker

请定义“满二叉树”。您似乎并不是指通常意义下的“满二叉树”。目前这个问题还不太清楚。 - John Dvorak

@JanDvorak 的 full tree 意味着每个内部节点都有两个子节点。 - Makara

@twalberg 这两种遍历方式都代表着同一棵树。 - Makara

Answer 1

不行，仅凭一个列表是不够的。想一想后序列表：4 5 2 3 1。

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

两棵树都有可能，但我们不知道哪一个生成了这个列表。

假设树中的每个元素都是唯一的，我们知道前序遍历是按照以下方式构建的：

[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

- Absurd-Mind

---

完全树指的是每个内部节点都有两个子节点，而这个树不满足这个条件。 - John Dvorak

@Makara，请定义“完整树”，然后。 - John Dvorak

@JanDvorak 先生，您在上面的评论中已经回答了这个问题。我的问题是，我们能否仅从后序遍历或前序遍历重构二叉树？ - Makara

我认为你无法从后序遍历和前序遍历重建一棵树，反例是：前序遍历-1,2；后序遍历-2,1 - Matej Briškár

然而，这只发生在左侧最子节点和右侧最子节点相同时，因为你无法确定它是右侧还是左侧的子节点。但是，对于“完全”二叉树，您可以重建树，因为不会出现这种情况。 - Matej Briškár

Answer 2

我稍微调整了一下顺序以更好地理解它们，以下是我的发现：

• 后序遍历 - 从序列中你总是可以知道什么是根节点和什么是最右边的子节点（例如1,2,3,4,5 - 5是根节点，4是最右边的子节点）
• 前序遍历 - 从序列中你总是可以知道什么是根节点和什么是最左边的子节点（例如1,2,3,4,5 - 1是根节点，2是最左边的子节点）
• 中序遍历 - 给定一个根节点，你总是可以知道左边和右边的内容（例如1,2,3,4,5和根节点3 - 1,2在左边，3,4,5在右边）

现在你可以玩它了。使用中序遍历和后序遍历或前序遍历，您可以轻松重建树，因为您可以找到根，并递归地为左/右分支始终找到它。如果同时具有前序遍历和后序遍历，则可以找到根节点、最左侧子节点和最右侧子节点。问题出现在根节点仅有左/右子节点的情况下，因为您无法确定哪个子节点是左侧还是右侧，因此不能轻松地重建树。

然而，如被要求的那样，拥有“完全”二叉树，其中每个顶点都具有两个子节点或任何一个子节点，您不会遇到前/后序组合的问题，因此每对顺序都将帮助您重建树。但是，只有一种顺序是不够的（例如，只知道左子节点是不够的，您没有关于哪一个是右子节点的信息）。

- Matej Briškár

Answer 3

假设你有一棵有3个节点且全部标记相同的树。至少有3个这样的（不一定是满的）树，但无论以何种顺序，它们都将具有相同的遍历数组。这应该回答了你的第一个问题。

- Scott Hunter

---

你的意思是说我们不能仅通过后序或前序数组得到一棵唯一的树，对吗？ - Makara

@Makara：即使你两者都有也不行。但请记住，这些树不一定是满的。 - Scott Hunter

@Makara：试试看吧！要考虑的情况并不是很多。但反例只能证明什么情况下行不通，而不能证明什么情况下行得通。 - Scott Hunter

是的，我尝试使用栈来实现。我发现当树中的元素是唯一的时候，我可以仅通过后序遍历数组和栈来构建它。 - Makara