大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
二叉树的前序遍历、中序遍历和后序遍历之间还原二叉树
1、概念
（1）前序遍历
a、访问根节点；b、前序遍历左子树；c、前序遍历右子树。
（2）中序遍历
a、中序遍历左子树；b、访问根节点；c、中序遍历右子树。
（3）后序遍历
a、后序遍历左子树；b、后续遍历右子树；c、访问根节点。
2、前序遍历和中序遍历还原二叉树
思想如下：
a、根据前序遍历结果，第一个元素为二叉树的根结点；
b、观察中序遍历结果，根结点左侧的为左子树，若左子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；根结点右侧的为右子树，若右子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；
c、上面的过程是递归的。先找到当前树的根结点，然后划分为左右子树，再进入左子树重复上面的过程，最后进入右子树重复上面的过程，最终还原一棵树。
例：
已知前序遍历：ABDHIEJKCFLMGNO
中序遍历：HDIBJEKALFMCNGO
按照上述步骤先画出二叉树，然后在进行求解后序遍历结果。结果为：HIDJKEBLMFNOGCA
练习：
1、前序遍历：GDAFEMHZ
中序遍历：ADEFGHMZ
求得后序遍历结果为：AEFDHZMG
2序遍历：ADCEFGHB
中序遍历：CDFEGHAB
求得后序遍历结果为：CFHGEDBA
3、中序遍历和后序遍历还原二叉树
思想如下：
a、根据后序遍历结果，最后一个元素为二叉树的根结点；
b、观察中序遍历结果，其中根结点左侧为左子树，若左子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；其中根结点右侧为右子树，若右子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；
c、上面的过程是递归的。先根据后序遍历结果找根结点，根结点左侧为左子树，右侧为右子树，再进入左子树重复上面的过程，最后进入右子树重复上面的过程，最终还原一棵树。
例：
已知
中序遍历：HDIBJEKALFMCNGO
后序遍历：
HIDJKEBLMFNOGCA
按照上述步骤先画出二叉树，然后在进行求解前序遍历结果。结果为：
ABDHIEJKCFLMGNO
练习：可参考前序遍历和中序遍历的练习
4、前序遍历和后序遍历还原二叉树
已知前序和中序，后序和中序遍历序列之后，可以唯一确定一棵二叉树。但是，只知道前序和后序遍历序列，是无法知道哪个结点是左子树还算右子树。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/193915.html原文链接：https://javaforall.net
