先AC,后面再优化!
#pragma GCC optimize(2)// 吸口氧气
#pragma GCC optimize(3)// 吸口臭氧
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 5E4 + 10;
int n, preorder[N], inorder[N];
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
~TreeNode() {
// 可以后面实现,但在面试时候,如果你写了表明至少你已经意识到了(be aware of)有内存泄漏的问题!
}
};
TreeNode* construct(int* preorder, int* inorder, int i, int j, int n) {
if (n <= 0) return (TreeNode*) nullptr;
if (n == 1) return new TreeNode(preorder[i]);
int k = j;
while (inorder[k] != preorder[i]) ++k;
const int l = k - j; // l == 左子树的长度 ...
auto root = new TreeNode(inorder[k]);
root->left = construct(preorder, inorder, i + 1, j, l);
root->right = construct(preorder, inorder, i + 1 + l, k + 1, n - l - 1);
return root;
}
TreeNode* buildTree(int* preorder, int* inorder) {
return construct(preorder, inorder, 0, 0, n);
}
void postOrder(TreeNode* root, vector<int>& v) {
if (!root) return;
postOrder(root->left, v);
postOrder(root->right, v);
v.emplace_back(root->val);
}
int main(void) {
cin >> n;
for (int i = 0; i < n; ++i) cin >> preorder[i];
for (int i = 0; i < n; ++i) cin >> inorder[i];
auto root = buildTree(preorder, inorder);
vector<int> v;
postOrder(root, v);
cout << v.front() << endl;
}