Recover a Tree From Preorder Traversal Solutions in C++

// Source : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
// Author : Ahmed Morsy
// Date   : 2019-05-29
// source : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/


/*  Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
*/  


class Solution {
public:

    TreeNode* recoverFromPreorder(string S) {
        vector<int>values,depth;
        int cur_val = 0 , cur_depth = 0;
        bool dash = false;
        for(char s : S){
            if(s == '-'){
                if(!dash){
                    values.push_back(cur_val);
                    depth.push_back(cur_depth);
                    cur_depth = 0;
                    cur_val = 0;
                }
                dash = true;
                cur_depth++;
            }
            else{
                dash = false;
                cur_val *= 10;
                cur_val += s-'0';
            }
        }
        values.push_back(cur_val);
        depth.push_back(cur_depth);

        unordered_map<TreeNode*,int>depths;


        int ptr = 1;
        TreeNode *root = new TreeNode(values[0]);
        depths[root] = 0;
        stack<TreeNode*>st;
        st.push(root);

        while(ptr < (int)values.size()){
            TreeNode *cur = st.top();
            if(depth[ptr] == depths[cur]+1 && (cur->left == NULL || cur->right == NULL)){
                TreeNode *t = new TreeNode(values[ptr++]);
                depths[t] = depths[cur]+1;
                if(cur->left == NULL){
                    cur->left = t;
                }
                else{
                    cur->right = t;
                }
                st.push(t);
            }
            else{
                st.pop();
            }
        }
        return root;

    }
};

/// Source : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
/// Author : liuyubobobo
/// Time   : 2019-04-13

#include <iostream>
#include <cassert>

using namespace std;


/// Recursion
/// Time Complexity: O(|s|^2)
/// Space Complexity: O(|s|)

/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        return build(S, 0);
    }

private:
    TreeNode* build(string s, int d){

        if(d >= s.size()) return NULL;

        assert(s[d] != '-');

        int num = first_number(s);
        TreeNode* root = new TreeNode(num);

        if(s.size()){
            int another = -1;
            for(int i = d + 1; i < s.size(); i ++)
                if(s[i] != '-' && ok(s, i + 1, d + 1)){
                    another = i + 1;
                    break;
                }

            if(another == -1) root->left = build(s, d + 1);
            else{
                root->left = build(s.substr(0, another), d + 1);
                root->right = build(s.substr(another), d + 1);
            }

        }
        return root;
    }

    int first_number(string& s){

        int digit = 0;
        for(; digit < s.size() && s[digit] == '-'; digit ++);

        int digit_end = digit + 1;
        for(;digit_end < s.size() && s[digit_end] != '-'; digit_end ++);

        string num_str = s.substr(digit, digit_end - digit);
        s = s.substr(digit_end);
        return atoi(num_str.c_str());
    }

    bool ok(const string& s, int start, int d){

        return ok(s.substr(start, d + 1), d);
    }

    bool ok(const string& s, int d){
        if(s.size() != d + 1) return false;
        for(int i = 0; i < s.size() - 1; i ++)
            if(s[i] != '-') return false;
        return s.back() != '-';
    }
};


int main() {

    Solution().recoverFromPreorder("1-401--349---90--88");

    return 0;
}