已知中序遍历和先序遍历求后序遍历
已知中序遍历和先序遍历求后序遍历
给一棵树的先序遍历和中序遍历如下：
先序遍历：ABCDEFGHI
后序遍历：CEDFBAHGI
后序遍历结果：EFDCBHIGA
首，先序遍历的过程为根-左-右，中序遍历的过程为左-根-中，后序遍历的过程为 左-右-根
由先序遍历过程可知先序遍历最开始的都是根，所以可以由先序遍历的根对应中序遍历中的根从而在中序遍历中对树进行划分。
划分结果
先序遍历的根：
A B C D E F G H I
下面是递归求解的过程，过程中注意每一个子区间代表一课子树，在判断子树根的位置时要考虑这棵子树是否有左子树或者右子树，对没有的情况要特判
#include<stdio.h> #include<cstring> #pragma warning(disable:4996) #define maxn 100000 using namespace std; char s1[maxn]; char s2[maxn]; void dfs(char root, int pos, int l, int r) { if (r - l <= 1) { if(root != ' ') printf("%c", root); return; } for (int i = l; i < r; i++) { if (s2[i] == root) { char t = pos + 1 < strlen(s1)&&i !=l ? s1[pos + 1] : ' ';//i == l 没有左子树 dfs(t, pos + 1, l, i); t = pos + 1 + i - l < strlen(s1)&&i!=r-1 ? s1[pos + 1 + i - l] : ' ';//i= r-1没有右子树 dfs(t, pos + 1 + i - l, i+1, r); printf("%c", root); } } } int main() { scanf("%s%s",s1,s2); int len1 = strlen(s1); int len2 = strlen(s2); char root = s1[0]; dfs(root, 0, 0, len2); getchar(); getchar(); return 0; }
你不勇敢，没人替你坚强！
版权声明：本文为zxzmnh原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。