为什么使用先序遍历、后序遍历和层次遍历无法构建二叉树？

Question

给定：

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

无法使用给出的12、23、31甚至123来构建二叉树！为什么呢？为什么中序遍历对于构建原始树非常重要？

- Prasath Govind

---

有两棵不同的树能够产生相同的前序遍历、后序遍历和层序遍历，找到一个例子是一个很好的练习。 - n. m.

Answer 1

没有中序遍历我们无法构建一棵树，为什么呢？假设你只有先序遍历和后序遍历。下面是一个简单的例子。
考虑两棵不同的树，

TREE 1:

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

第二棵树：

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

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

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

这是因为我们无法仅依靠前序或后序遍历来区分左子树和右子树。

前序遍历总是先访问根节点，然后是左子树和右子树。也就是说，通过遍历前序列表，在每个节点上停留时，它都是一个左/右子树的“根”。

后序遍历总是先访问左子树和右子树，然后是根节点。也就是说，反向遍历后序列表，在每个节点上停留时，它都是一个左/右子树的“根”。

相反，中序遍历总是先访问左子树，然后是根和右子树。这意味着，给定一个根节点（可以从上面提到的前序或后序遍历中获得），中序遍历告诉我们给定根节点的左右子树的大小，因此我们可以构建原始树。（请思考一下）

层序遍历也是同样的情况。因此，如果我们想要获得唯一的树，我们需要用中序遍历和三种遍历方式中的任何一种。

注 - 当然，全二叉树是例外情况，其中前序和后序遍历可用于构造树，因为树结构没有歧义。

- Rahul Nori