二叉树先序，中序，后序，层序遍历还原_层序遍历恢复二叉树

我们通过学习已经知道：若已知一棵二叉树的先（后）序遍历序列和中序遍历序列，则可以唯一还原出一棵二叉树。那么，
（1）如果知道一棵二叉树的先序遍历序列和后序遍历序列，是否可以唯一还原一棵二叉树？为什么？
（2）如果知道一棵二叉树的先序遍历序列和按层遍历序列，是否可以唯一还原一棵二叉树？为什么？
（3）如果知道一棵二叉树的中序遍历序列和按层遍历序列，是否可以唯一还原一棵二叉树？为什么？

中序遍历和后序遍历

可以，按层遍历顺序也是在将父节点与子结点进行分离，中序遍历向我们指明了左子树和右子树，因此可根据这两个序列明确父子关系以及左右位置。
此方法也适用于中序遍历和先序遍历
点此查看中序遍历和后序遍历还原

先序遍历和后序遍历

不可以，前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。 比如前序序列是ABC，后序序列是CBA。我们一定可以确定根节点是A，但接下来无法知道哪些属于左子树，哪些属于右子树，就会出现下图的情况。


先序遍历和层序遍历

不可以，按层遍历顺序也是在将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。 比如前序序列是ABC，层序序列是ABC。我们一定可以确定根节点是A，但接下来仍无法知道哪些属于左子树，哪些属于右子树，就会出现上图的情况。
此情况也适用于后序遍历和层序遍历

中序遍历和层序遍历

可以，按层遍历顺序也是在将父节点与子结点进行分离，中序遍历向我们指明了左子树和右子树，因此可根据这两个序列明确父子关系以及左右位置。
详细的方法可见：二叉树遍历序列还原·已知中序遍历和层序遍历