鼠标网站模板,网站建设报价表模板,深圳产品推广网站建设方案,科技助手题目 题目大意
给出一棵树的后序遍历和中序遍历#xff0c;要求输出该树的层序遍历。
思路
非常典型的树的构建与遍历问题。后序遍历和中序遍历可以得出一个树的结构#xff0c;用递归锁定根节点#xff0c;然后再遍历左右子树#xff0c;我之前发过类似题目的博客…题目 题目大意
给出一棵树的后序遍历和中序遍历要求输出该树的层序遍历。
思路
非常典型的树的构建与遍历问题。后序遍历和中序遍历可以得出一个树的结构用递归锁定根节点然后再遍历左右子树我之前发过类似题目的博客这里就不再详细赘述。层序遍历就是使用队列了。
代码
#include iostream
#include vector
#include queue
using namespace std;int n;
vectorint hou, mid, level;
struct node{int data;node * lchild, *rchild;
};void buildtree(node * root, int hl, int hr, int ml, int mr){if (hl hr || ml mr){return;}int pos;for (int i ml; i mr; i){if (hou[hr] mid[i]){pos i;break;}}root new node();root-data hou[hr];root-lchild root-rchild nullptr;buildtree(root-lchild, hl, hl pos - ml - 1, ml, pos - 1);buildtree(root-rchild, hl pos - ml, hr - 1, pos 1, mr);
}void findlevel(node * root){queuenode * q;q.push(root);while (!q.empty()){node * now q.front();level.push_back(now-data);q.pop();if (now-lchild) q.push(now-lchild);if (now-rchild) q.push(now-rchild);}
}int main(){cin n;hou.resize(n);mid.resize(n);for (int i 0; i n; i){cin hou[i];}for (int i 0; i n; i){cin mid[i];}node * root nullptr;buildtree(root, 0, n - 1, 0, n - 1);findlevel(root);for (int i 0; i (int)level.size(); i){if (i ! 0) cout ;cout level[i];}cout endl;return 0;
}
