共计 1926 个字符,预计需要花费 5 分钟才能阅读完成。
题目粗心:
给定一个二叉树的后序遍历和中序遍历, 要求输入层序遍历
算法思路:
首先由后序遍历和中序遍历构建此二叉树, 而后层序遍历二叉树.
构建二叉树的思路:
应用递归建设二叉树,假如递归过程中某步的后序区间是 $[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;
}
正文完