/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
if (preorder.size() == 0) {
return nullptr;
}
int val = preorder[0];
TreeNode *node = new TreeNode(val);
if (preorder.size() == 1) {
return node;
}
vector<int> prev1;
vector<int> postv1;
vector<int> prev2;
vector<int> postv2;
int tmp = preorder[1];
for (int i = 0; i < postorder.size()-1; i++) {
if (postorder[i] != tmp) {
prev1.push_back(preorder[i+1]);
postv1.push_back(postorder[i]);
} else {
prev1.push_back(preorder[i+1]);
postv1.push_back(postorder[i]);
for (int j = i+1; j < postorder.size()-1; j++) {
prev2.push_back(preorder[j+1]);
postv2.push_back(postorder[j]);
}
break;
}
}
node->left = constructFromPrePost(prev1, postv1);
node->right = constructFromPrePost(prev2, postv2);
return node;
}
};
思路
类似,递归处理,使用最直观的递归方式,时空效率并不高;