[PAT] A1099 Build A Binary Search Tree

题目大意

给出二叉搜索树的树型和各个节点值，求出该树的后序遍历结果。

思路

用静态结构体数组表示树。序列按照值从小到大即树的中序遍历结果。根据输入确定树型，在中序遍历的过程中填入值。接着层序遍历一次输出即可。（也可遍历时标记满二叉树情况下的index，根据index值从大到小输出即为层序遍历结果）

AC代码

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <cstdio> #include <vector> #include <map> #include<algorithm> #include<queue> #include <cstring> using namespace std; struct Node { int key; int lchild, rchild; }node[100]; vector<int>in; int t = 0; void in_insert(int v) { if (node[v].lchild != -1)in_insert(node[v].lchild); node[v].key = in[t]; t++; if (node[v].rchild != -1)in_insert(node[v].rchild); } void levelorder() { queue<int>q; q.push(0); bool space = false; while (!q.empty()) { int v = q.front(); q.pop(); if (space == false) { printf("%d", node[v].key); space = true; } else { printf(" %d", node[v].key); } if (node[v].lchild != -1)q.push(node[v].lchild); if (node[v].rchild != -1)q.push(node[v].rchild); } } bool cmp(int a, int b) { return a < b; } int main() { int n, i; scanf("%d", &n); for (i = 0;i < n;i++) { scanf("%d%d", &node[i].lchild, &node[i].rchild); } int value; for (i = 0;i < n;i++) { scanf("%d", &value); in.push_back(value); } sort(in.begin(), in.end(), cmp); in_insert(0); levelorder(); return 0; }

不用层次遍历，直接赋值index的方法。代码如下：

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <cstdio> #include <vector> #include <map> #include<algorithm> #include<queue> #include <cstring> using namespace std; struct Node { int key; int lchild, rchild; int index, lebel; }node[100]; vector<int>in; int t = 0; void in_insert(int v, int index, int lebel) { if (node[v].lchild != -1)in_insert(node[v].lchild, index * 2 + 1, lebel + 1); node[v].index = index; node[v].lebel = lebel; node[v].key = in[t]; t++; if (node[v].rchild != -1)in_insert(node[v].rchild, index * 2 + 2, lebel + 1); } bool cmp(int a, int b) { return a < b; } bool cmpindex(Node a, Node b) { if (a.lebel != b.lebel)return a.lebel < b.lebel; return a.index < b.index; } int main() { int n, i; scanf("%d", &n); for (i = 0;i < n;i++) { scanf("%d%d", &node[i].lchild, &node[i].rchild); } int value; for (i = 0;i < n;i++) { scanf("%d", &value); in.push_back(value); } sort(in.begin(), in.end(), cmp); in_insert(0, 0, 0); sort(node, node + n, cmpindex); printf("%d", node[0].key); for (i = 1;i < n;i++) printf(" %d", node[i].key); return 0; }

疑问：为啥如果不用lebel，就会有两个测试点（1、2）过不了？？？求路过的大神帮忙解答一下，万分感激！！！