为什么无法构造具有Pre-Order，Post Order和Level Order遍历的二叉树？

Question

鉴于：

12或23或31甚至给定123都无法构造二叉树！为什么是这样？以及为什么InOrder Traversal对构造原始树很重要？

Answer 1

没有中序遍历，我们就无法构建树。为什么？假设您获得了预购订单和 post 订单遍历 only.A 简单示例如下所示。
考虑两棵不同的树，

树 1：

root=a;  
root->left=b;  
root->left->right=c;

树 2：

root=a;  
root->right=b;  
root->right->left=c;

两棵树不同，但具有相同的预序和 post 序。

pre-order - a b c  
post-order - c b a

之所以如此，是因为我们无法单独使用前序或post序遍历来分离左子树和右子树。

Pre-order，顾名思义，总是先访问根节点，再访问左右子树。也就是说，遍历一个预序表，我们命中的每个节点都是一个 "root" 子树。

Post-order，顾名思义，总是先访问左右子树，再访问根。也就是说，向后遍历 post-order 列表，我们命中的每个节点将是子树的 "root"。

另一方面，按顺序总是先访问左子树，然后是根，然后是右子树，这意味着给定一个根（我们可以从预序或 post-order traversal as stated), in-order traversal告诉我们给定根的左右子树的大小，因此我们可以构造原始树。（思考一下）

层序遍历也是如此。因此，如果我们想要获得一棵唯一的树，我们需要一个中序遍历以及三个遍历中的任何其他遍历。
注意 - 例外当然是完整的二叉树，其中可以使用前序和 post 序遍历来构造树，因为树结构没有歧义。

Why it is impossible to construct Binary Tree with Pre-Order, Post Order and Level Order traversals given?