最近刷PAT老是碰到这种憨批题目,这种题目在算法面试中也是常客了,主要分为4类
- 已知前序 中序,求后序
- 已知前序 中序,求层次
- 已知后序 中序,求前序
- 已知前序 中序,求层次
而这四种题目如果要做出来的话,通通不需要建树,因为建树也是按照一定的递归顺序来的,就算是层次遍历,也可以在递归途中保存一些信息来获得.
我们先给出一颗二叉树
可以得到以下信息
- 前序:4,1,3,2,6,5,7
- 中序:1,2,3,4,5,6,7
- 后序:2,3,1,5,7,6,4
- 层次:4,1,6,3,5,7,2
前序&中序-->后序
利用递归,前序遍历的第一个永远是根,root表示根在前序数组中的index,left表示子树的左边界,right表示子树的右边界.第一次调用pos(0,0,6),然后在中序数组中找到分界点4,index=3.所以子树被分为了[left,index-1]和[index+1,right],也就是[0,2]和[4,6].root+1就是左子树根的下标,root+1+左子树数目\((i+1-left)\)就是右子树根的下标,然后递归即可.注意先递归左子树,再右子树,最后再输出当前节点.
前序 | 4 | 1 | 3 | 2 | 6 | 5 | 7 |
中序 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
int pre[]={4,1,3,2,6,5,7};
int mid[]={1,2,3,4,5,6,7};
void pos(int root,int left,int right)
{
//相等的话还是能输出一个,所以left>right再终结
if(left>right)return;
int i=left;
while(i<right&&mid[i]!=pre[root])i++;
pos(root+1,left,i-1);
pos(root+(i+1-left),i+1,right);
printf("%d ",pre[root]);
}
int main()
{
pos(0,0,6);
}
前序&中序-->层次
层次就是用来白给的,可以记录某个节点再完全二叉树的id号,然后排序输出即可得到,对于一个index的节点(index从0开始),左儿子为(\(index*2+1\)),右儿子为(\(index*2+2\)),然后扔进优先队列即可
#include <iostream>
#include<bits/stdc++.h>
#define each(a,b,c) for(int a=b;a<=c;a++)
#define de(x) cout<<#x<<" "<<(x)<<endl
using namespace std;
const int maxn=500+5;
const int inf=0x3f3f3f3f;
int pre[]={4,1,3,2,6,5,7};
int mid[]={1,2,3,4,5,6,7};
struct node
{
int value;
int index;
node(int v,int i):value(v),index(i){}
bool operator<(const node&r)const
{
return index>r.index;
}
};
priority_queue<node>Q;
void pos(int root,int left,int right,int index)
{
//相等的话还是能输出一个,所以left>right再终结
//de(pre[root]);
if(left>right)return;
int i=left;
while(i<right&&mid[i]!=pre[root])i++;
//de(pre[root]);
//de(index);
Q.push(node(pre[root],index));
pos(root+1,left,i-1,index*2+1);
pos(root+(i+1-left),i+1,right,index*2+2);
printf("%d ",pre[root]);
}
int main()
{
pos(0,0,6,0);
cout<<endl;
while(!Q.empty())
{
cout<<Q.top().value<<" ";
Q.pop();
}
}
后序&中序-->前序/层次
原理相同,修改一下递归下标,输出顺序和数组名字就可以了.
#include <iostream>
#include<bits/stdc++.h>
#define each(a,b,c) for(int a=b;a<=c;a++)
#define de(x) cout<<#x<<" "<<(x)<<endl
using namespace std;
const int maxn=500+5;
const int inf=0x3f3f3f3f;
int pos[]={2,3,1,5,7,6,4};
int mid[]={1,2,3,4,5,6,7};
struct node
{
int value;
int index;
node(int v,int i):value(v),index(i){}
bool operator<(const node&r)const
{
return index>r.index;
}
};
priority_queue<node>Q;
void pre(int root,int left,int right,int index)
{
//相等的话还是能输出一个,所以left>right再终结
//de(pre[root]);
if(left>right)return;
int i=left;
while(i<right&&mid[i]!=pos[root])i++;
//de(pre[root]);
//de(index);
Q.push(node(pos[root],index));
printf("%d ",pos[root]);
pre(root-(right+1-i),left,i-1,index*2+1);
pre(root-1,i+1,right,index*2+2);
}
int main()
{
pre(6,0,6,0);
cout<<endl;
while(!Q.empty())
{
cout<<Q.top().value<<" ";
Q.pop();
}
}