|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
1099 Build A Binary Search Tree
给定树,把二叉搜索树构造出来,再给出层序遍历…… 就直接模拟就行,二叉树的结构是给定的,按中序遍历的顺序由小到大填数即可。
- #include <cstdio>
- #include <cstring>
- #include <string>
- #include <queue>
- #include <algorithm>
- using namespace std;
- int left[105];
- int right[105];
- int a[105];
- int b[105];
- queue<int> q;
- void dfs(int now, int &x) {
- if (now < 0) {
- return;
- }
- dfs(left[now], x);
- b[now] = a[x++];
- dfs(right[now], x);
- }
- int main() {
- int n;
- scanf("%d", &n);
- for (int i = 0; i < n; ++i) {
- scanf("%d%d",&left【i】, &right【i】);
- }
- for (int i = 0; i < n; ++i) {
- scanf("%d", &a【i】);
- }
- sort(a, a + n);
- dfs(0, n = 0);
- bool mark = false;
- for (q.push(0); !q.empty(); q.pop()) {
- if (mark) {
- putchar(' ');
- }
- else {
- mark = true;
- }
- int x = q.front();
- printf("%d", b[x]);
- if (left[x] >= 0) {
- q.push(left[x]);
- }
- if (right[x] >= 0) {
- q.push(right[x]);
- }
- }
- puts("");
- return 0;
- }
复制代码
|
|