还原二叉树
想要还原一棵二叉树,需要知道两种序列
先序和中序
或后序和中序
例:已知先序和中序序列

1、首先通过先序序列找到根结点
2、在中序序列找到在先序序列中已经找到的根结点,先看中序序列根结点左边的所有元素
3、在先序序列中对比中序序列根结点左边的所有结点,这些结点在先序序列中排最靠前的就是下一个结点(例在找到根结点a后,先看中序序列,a左边的元素有c b e d
,再看先序序列,发现c b e d
中b排在了第一个,所以b就是a的左结点)
结果为:

后序和中序与先序和中序差别不大,只是从后往前找