已知二叉树前、中序遍历，求…

向右看齐 2022-08-25 05:28 154阅读 0赞

**原文地址：**[已知二叉树前、中序遍历，求它的后序遍历][Link 1] **作者：** [hongxian][]

这是我今天做网易笔试题最后的编程题所碰到的问题。由于考试时时间比较紧，写的代码难免有瑕疵。

sample input

ABDGCEF

DGBAECF

sample output

GDBEFCA

思路：比较容易想到的方法是把它还原为二叉树再进行后序遍历。不过这样就比较麻烦了。下面的方法跳过建树的过程直接求后序遍历的。时间复杂度为O(n^2),空间复杂度为O(n)。当然这不是最优的，本人已经想到改进的方法，可以把时间复杂度降到O(nlogn)。不过由于懒惰，所以就苟且用这个吧。实际上有简短的递归方法。所以仅当做一种另类的想法记录一下。

用一个order数组存中序遍历中的字符在后序遍历中的顺序，从大到小。比如sample input中所得的order为：5 6 4 0 3 1 2。

直接用上面的例子说明算法过程：

order=0 0 0 0 0 0 0

对于str1中的A，找出它在str2中的位置为4，它左右order的值都和4位置的order的值相同，说明它有左、右子树

改变order的值为：

2 2 2 0 1 1 1

对于str1中的B，找出它在str2中的位置3，它左order的值和当前order值相同，说明它有左子树，

改变order的值为：

3 3 2 0 1 1 1

对于str1中的D，找出它在str2中的位置1，改变order的值为：

3 4 2 0 1 1 1

对于str1中的G，找出它在str2中的位置2，改变order的值为：

3 4 2 0 1 1 1

对于str1中的C，找出它在str2中的位置6，改变order的值为：

5 6 4 0 3 1 2

....

处理完后就得到order的值为5 6 4 0 3 1 2，恰好是后序遍历中str2的字符被反问到的顺序（从大到小）。

代码：

\#include <iostream>  
\#include <string>  
using namespace std;

const int maxn=100;

int find(char c,char str\[\])  
\{  
int len=strlen(str);  
for (int i=0;i<len;i++)  
if (c==str\[i\]) return i;  
return len;  
\}

int main()  
\{  
char str1\[maxn\],str2\[maxn\],str\[maxn\];  
cin>>str1>>str2;//输入前、中序遍历  
int len=strlen(str1);  
if (len!=strlen(str2)) return -1;  
int order\[maxn\]=\{0\};//order初始化为0  
for (int i=0;i<len;i++)  
\{  
int k=find(str1\[i\],str2);//找到前序第i个字符在中序字符中的位置  
int t=0;  
if (k>0 && order\[k-1\]==order\[k\]) t++;//有左子树  
if (k<len-1 && order\[k+1\]==order\[k\]) t++;//有右子树

for (int j=0;j<len;j++) if (order\[j\]>order\[k\]) order\[j\]+=t;//对于上面一层的加深层数

if (t==2)  
\{  
for (int j=k-1;j>=0;j--) if (order\[j\]>=order\[k\]) order\[j\]+=t; else break;//左子树被访问顺序会比右子树快1，所以下面order\[j\]+=t-1;  
for (int j=k+1;j<len;j++) if (order\[j\]>=order\[k\]) order\[j\]+=t-1; else break;  
continue;  
\}

if (t==1)  
\{  
if (k>0 && order\[k-1\]==order\[k\])//有左子树  
for (int j=k-1;j>=0;j--) if (order\[k\]==order\[j\]) order\[j\]+=t; else break;  
if (k<len-1 && order\[k+1\]==order\[k\])//有右子树  
for (int j=k+1;j<len;j++) if (order\[k\]==order\[j\]) order\[j\]+=t; else break;  
\}  
\}

for (int i=0;i<len;i++)//映射中序为后序  
str\[len-order\[i\]-1\]=str2\[i\];

str\[len\]=0;  
cout<<str<<endl;//输出  
return 0;  
\}

[Link 1]: http://blog.sina.com.cn/s/blog_5b57a49b0100b9to.html
[hongxian]: http://blog.sina.com.cn/u/1532470427

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关已知二叉树遍历序列求树

二叉树，我们能够了解，已知二叉树后序遍历序列和中序遍历序列，或者是前序遍历序列与中序遍历序列，可以唯一确定一棵树；例 1：已知二叉树后序遍历序列是bfegcda，中序遍历序

朱雀/ 2023年07月22日 03:56/ 0 赞/ 138 阅读

相关二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）

![9ae3b38d3e56c024e830ca7a9395315b.png][] 之前的一篇随笔（[二叉树、前序遍历、中序遍历、后序遍历][Link 1]）只对二叉树的

秒速五厘米/ 2022年12月19日 00:53/ 0 赞/ 159 阅读

相关二叉树利用前序遍历和中序遍历求二叉树及二叉树的后序遍历

二叉树利用前序遍历和中序遍历求二叉树及二叉树的后序遍历二叉树的三种遍历分别是前序遍历，中序遍历以及后序遍历，遍历的核心在于根的位置，可以简记为：前序遍历->根，左

缺乏、安全感/ 2022年11月20日 09:38/ 0 赞/ 182 阅读

相关已知二叉树的中序遍历和前序遍历，…

假设有棵树，长下面这个样子，它的前序遍历，中序遍历，后续遍历都很容易知道。 ![已知二叉树的中序遍历和前序遍历，如何求后序遍历][sg_trans.gif] PreO

叁歲伎倆/ 2022年08月25日 05:28/ 0 赞/ 137 阅读

相关已知二叉树前、中序遍历，求…

原文地址：[已知二叉树前、中序遍历，求它的后序遍历][Link 1] 作者： [hongxian][] 这是我今天做网易笔试题最后的编程题所碰到的问题。由于考试时时间比较紧，

向右看齐/ 2022年08月25日 05:28/ 0 赞/ 155 阅读

相关已知二叉树先序遍历中序遍历求其后序遍历、重建二叉树

已知二叉树先序遍历中序遍历求其后序遍历 (注：已知中序遍历序列和剩下两种遍历序列中的一种都可以确定二叉树，即可得到另一种遍历序列，但是已知前序遍历和后

水深无声/ 2022年08月09日 01:53/ 0 赞/ 177 阅读

相关二叉树遍历（已知中序、先序求后序）

二叉树的遍历 Time Limit: 1000ms Memory Limit: 32768KB This problem will be judged on HRBU

灰太狼/ 2022年06月09日 10:38/ 0 赞/ 198 阅读

相关二叉树遍历（已知先序、中序求后序）

【例3-4】求后序遍历时间限制: 1000 ms 内存限制: 65536 KB 提交数: 11 通过数: 9 【题目描述】输入一棵二叉树的先

柔情只为你懂/ 2022年06月09日 10:30/ 0 赞/ 207 阅读

相关 LeetCode--已知前序遍历和中序遍历构造二叉树

题干：根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。例如，给出前序遍历 preorder = [3,9,20,15

雨点打透心脏的1/2处/ 2022年03月01日 03:40/ 0 赞/ 169 阅读

相关已知二叉树的中序和后序求前序

例子，后序遍历为 gbdehfca，中序遍历为 dgbaechf 后序遍历中的最后一个元素是根节点，a，然后查找中序中a的位置把中序遍历分成 dgb a echf

朱雀/ 2021年10月09日 03:44/ 0 赞/ 305 阅读