Content #
什么是扩展二叉树呢？对于一棵二叉树的任意节点（包括树根、树枝、树叶节点）：
- 如果该节点缺左子节点，就给它补一个左子节点。
- 如果该节点缺右子节点，就给它补一个右子节点。
- 如果该节点既缺左子节点又缺右子节点，就给它补一个左子节点和一个右子节点。
所补的子节点的值为一个特定的值，比如为一个“#”，补完子节点后生成的二叉树就称为原二叉树的扩展二叉树。
下图中，左侧是一棵二叉树，右侧为该二叉树的扩展二叉树。
单独知道前序、中序或后序遍历，都无法唯一确定一棵二叉树。
这里给出 2 条新结论：
-
如果给出一个扩展二叉树的前序或后序遍历序列，是能够唯一确定一棵二叉树的。下图中，右侧的扩展二叉树的前序遍历序列为“ABD###C#E##”，通过这个序列是可以唯一确定下图左侧这个二叉树的。你不妨根据这个序列绘制一下对应的二叉树，看是否能够验证该结论的正确性。
-
给出一个扩展二叉树的中序遍历序列，是无法唯一确定一棵二叉树的。如下图的两棵二叉树，他们的扩展二叉树中序遍历序列相同，都为“#C#B#A#”。
