题目粗心:
给定一个二叉树的后序遍历和中序遍历,要求输入层序遍历
算法思路:
首先由后序遍历和中序遍历构建此二叉树,而后层序遍历二叉树.
构建二叉树的思路:
应用递归建设二叉树,假如递归过程中某步的后序区间是$[beginPost,lastPost]$,中序区间是$[beginIn,lastIn]$,那么根节点为$post[lastPost]$,首先初始化根节点$root$,接着须要在中序遍历中找到根节点的地位$index_root$,而后计算左子树的个数leftTreeLen = index_root-beginIn
,这样左子树和右子树在后序和中序遍历中就离开了,紧接着就是左子树递归root->left = createTree(beginPost,beginPost+leftTreeLen-1,beginIn,index_root-1);
右子树递归root->right = createTree(beginPost+leftTreeLen,lastPost-1,index_root+1,lastIn);
递归的边界就是在区间长度小于0的时候间接返回空即可。
层序遍历的思路见代码:
void leverTraverse(Node* root){ queue<Node*> q; int num = 0;//输入节点的个数,用来管制空格输入 q.push(root); while (!q.empty()){ Node* t = q.front(); q.pop(); printf("%d",t->data); if(num<N-1) printf(" "); ++num; if(t->left!=nullptr){ q.push(t->left); } if(t->right!=nullptr){ q.push(t->right); } }}
留神点:
- 1、应用数组in在本地编译器上可能无奈输出数据,CLion上无奈应用,DEV却能够。
- 2、在子树递归的时候,左右子树的区间肯定得分清,不然会导致递归失败,什么都没有输入,并且还不报错。
- 3、空格的输入须要应用一个变量num统计输入的个数,当num<N-1的时候就输入空格
提交后果:
AC代码:
#include <cstdio>#include <queue>using namespace std;struct Node{ int data; Node* left; Node* right;};int N;// 节点个数int post[50],In[50];// 后序和中序遍历序列Node* createTree(int beginPost,int lastPost,int beginIn,int lastIn){ if(beginPost>lastPost){ return nullptr; } Node* root = new Node; root->data = post[lastPost]; // 首先找到根节点在中序序列的地位 int index_root; for (index_root = beginIn; index_root <= lastIn; ++index_root) { if(In[index_root]==root->data){ break; } } int leftTreeLen = index_root-beginIn;//左子树元素个数 root->left = createTree(beginPost,beginPost+leftTreeLen-1,beginIn,index_root-1); root->right = createTree(beginPost+leftTreeLen,lastPost-1,index_root+1,lastIn); return root;}void leverTraverse(Node* root){ queue<Node*> q; int num = 0;//输入节点的个数,用来管制空格输入 q.push(root); while (!q.empty()){ Node* t = q.front(); q.pop(); printf("%d",t->data); if(num<N-1) printf(" "); ++num; if(t->left!=nullptr){ q.push(t->left); } if(t->right!=nullptr){ q.push(t->right); } }}int main(){ scanf("%d",&N); for (int i = 0; i < N; ++i) { scanf("%d",&post[i]); } for (int j = 0; j < N; ++j) { scanf("%d",&In[j]); } Node* root = createTree(0,N-1,0,N-1); leverTraverse(root); return 0;}