大家好，又见面了，我是全栈君。
假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ，中序遍历序列为 DBGEHJACIF ，求前序遍历。
整体思路是这样的，由后序遍历找到每个节点，然后由中序遍历判断左右子树，将整个二叉树还原后写出前序遍历。
后序遍历的顺序知道，最后一个A是二叉树的根节点，
然后把中序遍历从A分成两段，A左边的是左子树，A右边的是右子树，
结果如下
然后看右边的子树，
从后序遍历知道，左子树的后序遍历为IFC,中序遍历为CIF
问题回到刚开始，重复之前的过程，由后序遍历知道根节点为C，把中序遍历从C分成两段，
左边是左子树，右边是右子树
也就是右边只有一个右子树，
然后再次重复以上过程，现在IF的后序遍历是IF,中序遍历是IF，说明
节点时F，I是F的左子树
这样，这棵二叉树的右子树就完全复原了，左子树的方法完全相同，就是一个递归过程，流程图如下
NEXT:
最后得到的完整二叉树如下：
然后写出前序遍历就可以了，是ABDEGHJCFI
用算法可以实现的，暂时留在这。
作者：jason0539
微博：http://weibo.com/2553717707
博客：http://blog.csdn.net/jason0539（转载请说明出处）
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/121363.html原文链接：https://javaforall.net
