还原二叉树

还原二叉树


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


例:已知先序和中序序列
还原二叉树


1、首先通过先序序列找到根结点

2、在中序序列找到在先序序列中已经找到的根结点,先看中序序列根结点左边的所有元素

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


结果为:
还原二叉树


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