题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/1478635126488367104
唉，今天的bug出在了下面这条语句。
if (tree[root_key].left * tree[root_key].right < 0) full_tree = false;
我写成了
full_tree = !(tree[root_key].left * tree[root_key].right < 0); // 这就会导致full_tree即便变成了false也有可能变回true。导致错判。
根据前序和中序构建二叉树
参考的柳神代码，灵活的点就在于，用下标表示数组区间，嗯，相比直接传数组的引用，轻了不少。
int build(int R, int start, int end, int fa) { // 1. post数组的最右边的位置；2. start, end : in数组的起始位置；3. 对于这题来说还需要记录父节点fa。
if (start > end) return -1;
int root_key = post[R], pos = start;
while (in[pos] != root_key && pos < end) pos++;
tree[root_key].level = tree[fa].level + 1;
tree[root_key].fa = fa;
tree[root_key].left = build(R - 1 - (end - pos), start, pos - 1, root_key); // 记住post的最后一个元素的下标一定要用 R 来相对计算，而不是只用 pos，不然在递归的过程中，即便前几层看不出什么，往后一定会发生错位。
tree[root_key].right = build(R - 1, pos + 1, end, root_key); // 下标的选择是经常容易出bug的，一定要想清楚
if (tree[root_key].left * tree[root_key].right < 0) full_tree = false;
return root_key;
}
题解代码：
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
int n, m;
struct Node {
Node() {
fa = left = right = -1;
}
int level, fa, left, right;
} tree[1005];
bool full_tree = true;
int in[35], post[35], num1, num2;
int build(int R, int start, int end, int fa) { // 1. post数组的最右边的位置；2. start, end : in数组的起始位置；3. 对于这题来说还需要记录父节点fa。
if (start > end) return -1;
int root_key = post[R], pos = start;
while (in[pos] != root_key && pos < end) pos++;
tree[root_key].level = tree[fa].level + 1;
tree[root_key].fa = fa;
tree[root_key].left = build(R - 1 - (end - pos), start, pos - 1, root_key); // 记住post的最后一个元素的下标一定要用 R 来相对计算，而不是只用 pos，不然在递归的过程中，即便前几层看不出什么，往后一定会发生错位。
tree[root_key].right = build(R - 1, pos + 1, end, root_key); // 下标的选择是经常容易出bug的，一定要想清楚
if (tree[root_key].left * tree[root_key].right < 0) full_tree = false;
return root_key;
}
bool siblings(int a, int b) {
return tree[a].fa == tree[b].fa;
}
bool same_level(int a, int b) {
return tree[a].level == tree[b].level;
}
bool parent(int a, int b) {
return tree[b].fa == a;
}
bool left_child(int a, int b) {
return tree[b].left == a;
}
bool right_child(int a, int b) {
return tree[b].right == a;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> post[i];
for (int i = 0; i < n; i++) cin >> in[i];
int root = post[n - 1];
build(n - 1, 0, n - 1, 0);
cin >> m;
while (m--) {
string str;
cin >> str;
if (str[0] == 'I') {
getline(cin, str);
cout << (full_tree ? "Yes" : "No") << endl;
} else {
num1 = stoi(str);
cin >> str;
if (str[0] == 'a') {
cin >> num2 >> str >> str;
if (str[0] == 's') {
cout << (siblings(num1, num2) ? "Yes" : "No") << endl;
} else {
getline(cin, str);
cout << (same_level(num1, num2) ? "Yes" : "No") << endl;
}
} else {
cin >> str >> str;
switch(str[1]) {
case 'o' : {
cout << (root == num1 ? "Yes" : "No") << endl;
} break;
case 'a' : {
cin >> str >> num2;
cout << (parent(num1, num2) ? "Yes" : "No") << endl;
} break;
case 'e' : {
cin >> str >> str >> num2;
cout << (left_child(num1, num2) ? "Yes" : "No") << endl;
} break;
case 'i' : {
cin >> str >> str >> num2;
cout << (right_child(num1, num2) ? "Yes" : "No") << endl;
} break;
}
}
}
}
return 0;
}
刚做的时候以为要用层序遍历，顺便复习一下吧。
层序遍历模板代码：
vector<vector<int>> level_order(Node *root) {
vector<vector<int>> res;
queue<Node *> q;
if (root) q.push(root);
while (q.size()) {
int size = q.size();
vector<int> v;
for (int i = 0; i < size; i++) {
Node *node = q.front();
q.pop();
// 上一排的元素依次出队
v.push_back(node->val);
// 下一排的节点全部入队
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
// 存入一排
res.push_back(v);
}
return res;
}