// 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 a) {
        vector<TreeNode*> st;
        int i = 0, n = a.length();

        while (i < n){
            int d = 0;
            while(i < n && a[i] == '-'){
                i += 1;
                d += 1;
            }
            string cur = "";
            while (i < n && isdigit(a[i])){
                cur += a[i];
                i++;
            }
            TreeNode* val = new TreeNode(std::stoi(cur));

            while(st.size() > d){
                st.pop_back();
            }

            if(!st.empty()){
                if(st.back()->left == NULL){
                    st.back()->left = val;
                }
                else{
                    // assert(st.back()->right == NULL);
                    st.back()->right = val;
                }
            }
            st.push_back(val);
        }
        // assert(st.size());
        return st.front();
    }
};