algorithm - 为什么给定前序、后序、层序遍历就无法构造二叉树？

Question

给定:

1. 预序遍历。
2. 后序遍历。
3. 层序遍历。

不能用 12 或 23 或 31 甚至给定 123 来构造二叉树!为什么是这样？以及为什么 InOrder Traversal 对于构建原始树非常重要？

Answer 1

如果没有中序遍历，我们就无法构建树。为什么？假设您只获得了前序和后序遍历。下面显示了一个简单的示例。
考虑两棵不同的树，

树 1:

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

树 2:

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

两棵树都不同，但具有相同的前序和后序序列。

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

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

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

后序，顾名思义，总是先访问左右子树，再访问根。也就是说，向后遍历后序列表，我们命中的每个节点都是子树的“根”。

另一方面，按顺序总是先访问左子树，然后是根，然后是右子树，这意味着给定一个根(我们可以从前序或后序遍历中获得如上所述)，中序遍历告诉我们给定根的左右子树的大小，因此我们可以构造原始树。(思考一下)

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