889.
換用stack做
舒適又自在
不用翻 我只是覺得這樣可能比較
其實也沒有比較好看
/**
* 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>& pre, vector<int>& post) {
ranges::reverse(post);
auto rev = post;
int n = pre.size();
vector<int> pos(31, -1);
for(int i = 0; i < n; i++){
pos[rev[i]] = i;
}
stack<int> indice;
stack<TreeNode*> level;
indice.push(0);
TreeNode* root = new TreeNode(pre[0]);
TreeNode* nd = root;
level.push(nd);
int idx = 1;
while(idx < n){
//cout << idx << " ";
int val = pre[idx];
while(pos[val] < indice.top()){
indice.pop();
level.pop();
}
nd = level.top();
if(!nd->left){
nd->left = new TreeNode(val);
nd = nd->left;
}
else{
nd->right = new TreeNode(val);
nd = nd->right;
}
indice.push(pos[val]);
level.push(nd);
idx++;
}
return root;
}
};