您的当前位置：首页>信息资讯 > 正文

当前热讯：1159 Structure of a Binary Tree + 根据前序和中序构建二叉树+ 层序遍历模板复习

2023-05-03 18:18:57 来源：博客园

【资料图】

题目链接：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;}

标签：