前序遍历:根节点 -> 左子树 -> 右子树
中序遍历:左子树 -> 根节点 -> 右子树
题目代码
中序遍历:左子树 -> 根节点 -> 右子树
后序遍历:左子树 -> 右子树 -> 根节点
步骤:
1.找根节点
2.确定左右子树范围
3.把子树当做一棵树递归求解
建树代码
makeTree(先序,中序,长度){ if 长度==0 return 空 else 新建节点 for 找到pre[0]=mid[i] tree[当前].left=makeTree(左子树); tree[当前].righr=makeTree(右子树); return 当前; }
struct Node{ int date; int left,right; }; Node tree[50]; int cnt=0; int makeTree(int pre[],int mid[],int len){ if(len==0) return -1; int id=cnt++; tree[id].date=pre[0]; int i; for(i=0;mid[i]!=pre[0];i++) ; tree[id].left=makeTree(pre+1,mid,i); tree[id].right=makeTree(pre+i+1,mid+i+1,len-i-1); return id; } //tree[0]是根节点
int cnt=0; int makeTree(int la,int ra,int lb,int rb){//中序左,右,先序左,右 if(la>ra) return -1; int id=cnt++; tree[id].date=pre[lb]; int i; for(i=la;pre[lb]!=mid[i];i++) ; int len=i-la;//左子树长度 tree[id].left=makeTree(la,i-1,lb+1,lb+len); tree[id].right=makeTree(i+1,ra,lb+1+len,rb); return id; }
#include <bits/stdc++.h> using namespace std; struct Node{ int date; int left,right; }; Node tree[50]; int n; int pre[50],mid[50]; int cnt=-1; int makeTree(int pre[],int mid[],int len){ if(len==0) return -1; int id=++cnt; tree[id].date=pre[0]; int i; for(i=0;mid[i]!=pre[0];i++) ; tree[id].left=makeTree(pre+1,mid,i); tree[id].right=makeTree(pre+i+1,mid+i+1,len-i-1); return id; } void mirror(int id){ swap(tree[id].left,tree[id].right); if(tree[id].left!=-1) mirror(tree[id].left); if(tree[id].right!=-1) mirror(tree[id].right); } queue<int> q; void bfs(){ q.push(0); while(q.size()){ Node t=tree[q.front()]; q.pop(); if(t.date!=pre[0]) printf(" "); printf("%d",t.date); if(t.left!=-1) q.push(t.left); if(t.right!=-1) q.push(t.right); } } void dfs(int id){ cout<<tree[id].date<<" "; if(tree[id].left!=-1) dfs(tree[id].left); if(tree[id].right!=-1) dfs(tree[id].right); } int main(int argc, char** argv) { cin>>n; for(int i=0;i<n;i++) cin>>mid[i]; for(int i=0;i<n;i++) cin>>pre[i]; makeTree(pre,mid,n); mirror(0); bfs(); return 0; }