1028

/**
 * 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 S) {
        vector<TreeNode*> stk;
        for(int i=0, val, level; i<S.length();){
            // Get the level.
            for(level=0; S[i]=='-'; i++)
                level++;

            // Get the value.
            for(val=0; S[i]!='-' && i<S.length(); i++)
                val = val*10 + S[i]-'0';

            //Get the appropriate level in stack.
            while(stk.size() > level) stk.pop_back();

            // Create the node.
            TreeNode *node = new TreeNode(val);

            // If stack is not empty, insert at left or right appropriately.
            if(!stk.empty()){
                TreeNode *last = stk.back();
                if(!last->left) last->left = node;
                else if(!last->right) last->right = node;
            }
            stk.push_back(node);
        }
        return stk.front();
    }
};