《根据二叉树的后序遍历和中序遍历还原二叉树解题方法.pdf》由会员分享，可在线阅读，更多相关《根据二叉树的后序遍历和中序遍历还原二叉树解题方法.pdf（5页珍藏版）》请在三一文库上搜索。
1、【题目】 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ，中序遍历序列为 DBGEHJACIF ，则 其前序 遍历序列为 ( ) 。 A. ABCDEFGHIJ B. ABDEGHJCFI C. ABDEGHJFIC D. ABDEGJHCFI 由题，后序遍历的最后一个值为 A，说明本二叉树以节点 A 为根节点（当然，答案中第一 个节点都是 A，也证明了这一点） 下面给出整个分析过程 【第一步】 由后序遍历的最后一个节点可知本树根节点为【A】 加上中序遍历的结果， 得知以 【A】 为根节点时， 中序遍历结果被 【A】 分为两部分 【DBGEHJ】 【A】 【CIF】 于是作出第一幅图如
2、下 【第二步】 将已经确定了的节点从后序遍历结果中分割出去 即【DGJHEBIFC】-【A】 此时，位于后序遍历结果中的最后一个值为【C】 说明节点【C】是某棵子树的根节点 又由于【第一步】中【C】处于右子树，因此得到， 【C】是右子树的根节点 于是回到中序遍历结果【DBGEHJ】 【A】 【CIF】中来，在【CIF】中，由于【C】是根节点， 所以【IF】都是这棵子树的右子树， 【CIF】子树没有左子树，于是得到下图 【第三步】 将已经确定了的节点从后序遍历中分割出去 即【DGJHEBIF】-【CA】 此时，位于后序遍历结果中的最后一个值为【F】 说明节点【F】是某棵子树的根节点 又由于【第二
3、步】中【F】处于右子树，因此得到， 【F】是该右子树的根节点 于是回到中序遍历结果【DBGEHJ】 【A】 【C】 【IF】中来，在【IF】中，由于【F】是根节点， 所以【I】是【IF】这棵子树的左子树，于是得到下图 【第四步】 将已经确定了的节点从后序遍历中分割出去 即【DGJHEB】-【IFCA】 此时，位于后序遍历结果中的最后一个值为【B】 说明节点【B】是某棵子树的根节点 又由于【第一步】中【B】处于【A】的左子树，因此得到， 【B】是该左子树的根节点 于是回到中序遍历结果【DBGEHJ】 【A】 【C】 【F】 【I】中来，根据【B】为根节点，可以将 中序遍历再次划分为【D】 【B】
4、 【GEHJ】 【A】 【C】 【F】 【I】 ，于是得到下图 【第五步】 将已经确定了的节点从后序遍历中分割出去 即【DGJHE】-【BIFCA】 此时，位于后序遍历结果中的最后一个值为【E】 说明节点【E】是某棵子树的根节点 又由于【第四步】中【E】处于【B】的右子树，因此得到， 【E】是该右子树的根节点 于是回到中序遍历结果【D】 【B】 【GEHJ】 【A】 【C】 【F】 【I】中来，根据【B】为根节点， 可以将中序遍历再次划分为【D】 【B】 【G】 【E】 【HJ】 【A】 【C】 【F】 【I】 ，于是得到下图 【第六步】 将已经确定了的节点从后序遍历中分割出去 即【DGJH】-【EBIFCA】 此时，位于后序遍历结果中的最后一个值为【H】 说明节点【H】是某棵子树的根节点 又由于【第五步】中【H】处于【E】的右子树，因此得到， 【H】是该右子树的根节点 于是回到中序遍历结果【D】 【B】 【G】 【E】 【HJ】 【A】 【C】 【F】 【I】中来，根据【H】为根 节点，可以将中序遍历再次划分为【D】 【B】 【G】 【E】 【H】 【J】 【A】 【C】 【F】 【I】 ，于是得 到下图 至此，整棵二叉树已经还原 现在对该二叉树迚行前序遍历便能得到我们想要的答案 【B】