根据先序序列和中序序列确定唯一二叉树

1. 原文:

【教程】已知二叉树的先序序列和中序序列构造二叉树_立志Java工程师的博客-CSDN博客_已知先序序列和中序序列怎么画二叉树

2. 例:

已知某二叉树的先序序列为ABDGCEF，中序序列为DGBAECF

3. 梗概:

1. 采用嵌套的思想
2. 从外层到里层确定左右子树,
   1. 并且每一层的左右子树都要标出来, 要不容易乱

4. 步骤:

1. 根据先序遍历确定整个树的根
   1. A是该二叉树根节点
2. 根据中序遍历确定最外层树的左右子树
   1. DGB在A的左边，为第二层左子树
   2. ECF在A右边, 为第二层右子树
3. 根据先序遍历确定第二层左子树的根
   1. DGB左子树在先序遍历的顺序为BDG, 所以根为B
4. 根据中序遍历确定第二层左子树的左右子树
   1. DG在B的左边, 为第三层左子树
   2. B右边什么也没有, 没有第三层右子树
5. 根据先序遍历确定第三层左子树的根
   1. …D为第三层左子树的根
6. 根据中序遍历确定第三层左子树的左右子树
   1. G在B的右边, 为第四层左子树, 同时也是叶结点
   2. B右边什么也没有, 没有第四层右子树
7. 继续重复以上步骤, 直到每个结点位置都确定