题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

int n;
vector<int> PostOrder, InOrder ;
unordered_map<int,int> hash_in;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x),left(nullptr),right(nullptr){}
};

TreeNode* dfs(int postl ,int postr ,int inl ,int inr){
    TreeNode *root = new TreeNode(PostOrder[postr]);
    //根节点在中序遍历中的下标
    int k = hash_in[root->val];
    // k - inl表示左子树宽度
    // 先判断左子树存不存在
    if(inl < k) root->left = dfs(postl , postl + k -inl - 1 ,inl ,k - 1);
    if(inr > k) root->right = dfs(postl + k -inl , postr - 1 ,k + 1 ,inr );

    return root;
}

void bfs(TreeNode* root){
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode *tmp = q.front();
        q.pop();
        cout << tmp->val << " ";
        if(tmp->left) q.push(tmp->left);
        if(tmp->right) q.push(tmp->right);
    }
}

int main(){
    cin >> n;

    for(int i = 0 ; i < n; i++){
        int x ;
        cin >> x;
        PostOrder.push_back(x);
    }
    for(int i = 0 ; i < n; i++){
        int x ;
        cin >> x;
        InOrder.push_back(x);
        hash_in[x] = i;
    }
    TreeNode *head = dfs( 0 , n - 1, 0 , n - 1);

    bfs(head);
    return 0;
}