# leetcode 1028

## 思路

先畫一下圖，注意節點的深度是遞增的，減少的話用 callstack 來反推就好，簡單易處理，最後字串的處理一樣選用 stringstream 來處理，簡單又方便。

用 preorder 的方式走訪一次，並且讀取下一個 -- 連續的數量，如果層級相同時才做事否則直接 return ，以此類推即可。

// Time:  O(n)
// Space: O(h)

class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        if (S.empty())
            return nullptr;
        regex reg("(-*)([0-9]*)");
        input = istringstream(regex_replace(S, reg, "$1 $2 "));
        //cout << regex_replace(S, reg, "$1 $2 ") << endl;
        return recoverHelper(0);
    }
private:
    istringstream input;
    int nextLevel = 0;
    TreeNode* recoverHelper(int curLevel) {

        if (curLevel > nextLevel) {
            return nullptr;
        }
        int val;
        input >> val;
        //cout << val << " " << curLevel << endl;
        auto root = new TreeNode(val);
        string next;
        input >> next;
        nextLevel = next.size();
        
        root->left = recoverHelper(curLevel+1);
        root->right = recoverHelper(curLevel+1);
        return root;
    }
};