(資料圖片僅供參考)
題目鏈接：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#include#include#includeusing 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> level_order(Node *root) { vector> res; queue q; if (root) q.push(root); while (q.size()) { int size = q.size(); vector 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;} 關鍵詞：
