题目描述

样例

给自己收藏用的，不是题解，请谅解！

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
// char inorder[N], corder[N];
unordered_map<char, int>f;
string pre;
bool st[30];

struct TreeNode{
  char val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(char x): val(x), left(NULL), right(NULL){}
};

void dfs(TreeNode* root)
{
    if (!root) return;
    pre += root->val;
    dfs(root->left);
    dfs(root->right);
}

int main()
{
    string inorder, corder;
    cin >> inorder >> corder;
    for (int i = 0; i < inorder.size(); i ++) f[inorder[i]] = i;
    TreeNode* q[30];
    q[0] = new TreeNode(corder[0]);
    int i = 0, j = 1;
    while (j < corder.size())
    {
        int end = j;
        while (i < end)
        {
            int p = f[corder[i]];
            st[p] = true;
            if (p > 0 && !st[p - 1])
            {
                TreeNode* nq = new TreeNode(corder[j]);
                q[i]->left = nq;
                q[j ++] = nq;
            }
            if (p < corder.size() - 1 && !st[p + 1])
            {
                TreeNode* nq = new TreeNode(corder[j]);
                q[i]->right = nq;
                q[j ++] = nq;
            }
            i ++;
        }

    }
    dfs(q[0]);
    cout << pre << endl;

    return 0;
}