先序中序后序遍历二叉树⼆叉树知道前序、中序求后序序列
思路：
【1】根据前序性质，每⼀颗⼦树的前序第⼀个节点永远是其根节点（后序也有类似性质，所以知道后序中序求前序是⼀个道理）。
【2】根据中序性质，在中序序列中，某节点之前的节点全在其左边，反之在其右边。
那么我们在前序序列中到当前树根节点时，再在中序序列中到树根节点的位置，那么知道中序序列中，在根节点以前的节点都是其左⼦树，之后的是右⼦树，这样就可以递归建这两棵树，这⾥我们选择直接打印后序序列，打印顺序为递归左⼦树，递归右⼦树，打印⾃⾝。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
vector<int> ans;
vector<int> v1,v2;
void dfs(int a,int b,int cnt) {
if(cnt == 1) {
ans.push_back(v1[a]);
return;
}
else if(cnt <= 0) return;
int i;
for(i=0;v1[a] != v2[b+i];i++);
dfs(a+1,b,i);
dfs(a+i+1,b+i+1,cnt-i-1);
ans.push_back(v1[a]);
return;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF) {
v1.clear();
v2.clear();
ans.clear();
int num;
for(int i=0;i<n;i++) {
scanf("%d",&num);
v1.push_back(num);
}
for(int i=0;i<n;i++) {
scanf("%d",&num);
v2.push_back(num);
}
dfs(0,0,n);
printf("%d",ans[0]);
for(int i=1;i<ans.size();i++)
printf(" %d",ans[i]);
puts("");
}
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。