1028.
traversal而已
感覺要算簡單的medium==
寫起來醜醜的
一個好好的遞回為啥被搞的這麼複雜
看人家用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* recoverFromPreorder(string t) {
TreeNode* root = new TreeNode();
TreeNode* nd = root;
int cur = 0;// current depth
int idx = 0;
vector<int> ds, vs;
while(true){
auto [d, val] = next(idx, t);
if(val <= 0) break;
ds.push_back(d);
vs.push_back(val);
}
idx = 0;
build(nd, cur, ds, vs, idx);
return root;
}
void build(TreeNode* nd, int cur, vector<int>& ds, vector<int>& vs, int& idx){
if(idx >= ds.size()) return;
if(ds[idx] == cur){
nd->val = vs[idx];
idx++;
}
if(idx >= ds.size()) return;
if(ds[idx] > ds[idx-1]){
if(!nd->left){
nd->left = new TreeNode();
build(nd->left, cur+1, ds, vs, idx);
}
else{
nd->right = new TreeNode();
build(nd->right, cur+1, ds, vs, idx);
}
}
if(idx >= ds.size()) return;
if(ds[idx] > cur){
nd->right = new TreeNode();
build(nd->right, cur+1, ds, vs, idx);
}
}
pair<int, int> next(int& idx, string& t){
int d = 0, val = 0, n = t.length();
if(idx >= n) return {-1, -1};
while(t[idx] == '-') {
idx++;
d++;
}
while(idx < n and t[idx] != '-') {
val *= 10;
val += t[idx] - '0';
idx++;
}
return {d, val};
}
};