给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构

原题： 18. 重建二叉树

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    unordered_map<int,int> pos;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i ++) {
            pos[inorder[i]] = i;
        }
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir) {
        if (pl > pr) {
            return NULL;
        }
        int k = pos[pre[pl]];
        TreeNode* root = new TreeNode(pre[pl]);
        root->left = dfs(pre, in, pl + 1, pl + k - il, il, k - 1);
        root->right = dfs(pre, in, pl + k - il + 1, pr, k + 1, ir);
        return root;
    }
};

原题： 1497. 树的遍历

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = 30 + 5;

int n, postorder[N], inorder[N];
unordered_map<int, int> l, r, pos;

// 通过后序遍历和中序遍历，构造二叉树
int build(int il, int ir, int pl, int pr) {
    int root = postorder[pr];
    int k = pos[root];
    if (il < k) {
        l[root] = build(il, k - 1, pl, pl + k - il - 1);
    }
    if (ir > k) {
        r[root] = build(k + 1, ir, pl + k - il, pr - 1);
    }
    return root;
}

// 层序遍历
void bfs(int root) {
    queue<int> q;
    q.push(root);
    while (q.size()) {
        auto t = q.front();
        q.pop();
        cout << t << ' ';
        if (l.count(t)) {
            q.push(l[t]);
        }
        if (r.count(t)) {
            q.push(r[t]);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> postorder[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
        pos[inorder[i]] = i;
    }
    int root = build(0, n - 1, 0, n - 1);
    bfs(root);
    return 0;
}

原题： 1259. 二叉树遍历

给出中序和按层遍历的字符串，求该树的先序遍历字符串

待续整理中…