當前快看：1159 Structure of a Binary Tree + 根據(jù)前序和中序構建二叉樹+ 層序遍歷模板復習

int build(int R, int start, int end, int fa) { // 1. post數(shù)組的最右邊的位置；2. start, end : in數(shù)組的起始位置
；3. 對于這題來說還需要記錄父節(jié)點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
，不然在遞歸的過程中
，即便前幾層看不出什么，往后一定會發(fā)生錯位
。    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數(shù)組的最右邊的位置；2. start, end : in數(shù)組的起始位置
；3. 對于這題來說還需要記錄父節(jié)點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
，不然在遞歸的過程中
，即便前幾層看不出什么，往后一定會發(fā)生錯位
。    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);            // 下一排的節(jié)點全部入隊            if (node->left) q.push(node->left);            if (node->right) q.push(node->right);        }        // 存入一排        res.push_back(v);    }    return res;}