二叉树重构

问题：二叉树的中序遍历序列和后序遍历序列，求层次遍历序列
解决方案：考虑重构二叉树，再利用BFS求层次遍历序列

写此分享，仅供日后复习所用

C++代码：

#include<map>
#include<queue>
#include<set>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int after[40], in[40];
struct TreeNode {
    struct TreeNode* left;
    struct TreeNode* right;
    int val;
};
TreeNode* build(int* in, int* after, int length)
{
    if (length == 0) return NULL;
    TreeNode* node = new TreeNode;
    node->val = *(after + length - 1);
    //cout << node->val << " ";
    int index = 0;
    for (;index < length;index++)
    {
        if (in[index] == *(after + length - 1))
        {
            break;
        }
    }
    node->left = build(in, after, index);
    node->right = build(in + index + 1, after + index, length - (index + 1));
    return node;
}
void level(TreeNode* root)
{
    queue<TreeNode*> q;
    q.push(root);
    bool flag = false;
    while (q.size())
    {
        auto t = q.front();q.pop();
        if (t != NULL)
        {
            if (!flag)
            {
                cout << t->val;
            }
            else cout << " " << t->val;
            flag = true;
        }
        if (t->left != NULL) q.push(t->left);
        if (t->right != NULL) q.push(t->right);

    }
}
int n;
int main()
{
    cin >> n;
    for (int i = 0;i < n;i++) cin >> after[i];
    for (int i = 0;i < n;i++) cin >> in[i];
    TreeNode* root = build(in, after, n);
    level(root);
    return 0;
}

另一种写法：
原题链接

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int mid[40], last[40];//中序和后序
vector<int> res;//存储层次遍历的答案
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int val) {
        this->val = val;
        left = nullptr;
        right = nullptr;
    }
};
TreeNode* build(int l, int r, int& idx) {
    //idx指的是当前根节点的位置,l,r指的是根据中序遍历找出的处理区间
    //cout << "debug: " << l << "   " << r << endl;
    if (l > r) return nullptr;
    int key = last[idx--];
    TreeNode* root = new TreeNode(key);
    if (l == r) return root;
    int i;
    for (i = l; key != mid[i];i++);
    root->right = build(i + 1, r, idx);
    root->left = build(l, i - 1, idx);
    return root;
}
void bfs(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (q.size()) {
        auto t = q.front();q.pop();
        res.push_back(t->val);
        if (t->left != nullptr) q.push(t->left);
        if (t->right != nullptr) q.push(t->right);
    }
}
int main()
{
    int n; cin >> n;
    for (int i = 0;i < n;i++) cin >> last[i];
    for (int i = 0;i < n;i++)cin >> mid[i];
    int idx = n - 1;
    TreeNode* root = build(0, n - 1, idx);
    /*cout << root->val << endl;
    cout << root->left->val << endl;
    cout << root->right->val << endl;*/
    bfs(root);
    for (int i = 0;i < res.size();i++) {
        if (i != 0) cout << " ";
        cout << res[i];
    }
    return 0;
}