前言
要知道怎么进行二叉树还原,首先要知道二叉树先序排列,中序排列,后序排列的概念
下面的地址是关于先序排列,中序排列,后序排列的一些概念
在进行还原之前应该先搞懂这些
地址:https://blog.csdn.net/qq_33243189/article/details/80222629
接下来我们开始做一道关于二叉树还原的题
已知,我们知道一个二叉树的先序和中序排列
先序:ABDFGHIEC
中序:FDHGIBEAC
通过先序排列的A开头可知,二叉树的根节点是A,那么根节点左边的所有字母为FDHGIBE,又根据中序排列F开头可知左边根节点到F截止,如下图所示
图片.png
通过图片可知.FD和B之间夹杂了HGI等字母,所以判断HGI在D的右节点
图片.png
那么HGI在D的右节点该怎么排列呢,通过先序排列ABDF之后的GHI可知,G是GHI的根节点,那么.H就在G的根节点左边,I在G的根节点右边
如下图所示
图片.png
这里看着中序排列数字就可知,ADHGIB和根节点A之前还应该有一个E的节点
图片.png
到这里基本就完事了,因为只剩了一个c节点在根节点的右边
图片.png
到这里就完成了二叉树的整体还原
