Re: [閒聊] 每日leetcode
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;
}
};
-----
Sent from JPTT on my iPad
--
很姆的咪
姆之咪
http://i.imgur.com/5sw7QOj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1740325961.A.EE7.html
→
02/24 07:29,
9月前
, 1F
02/24 07:29, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1344 之 1552 篇)：