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() : 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* go_deep(vector<pair<int,int>>& arr,int ind, int depth)
    {
        if(ind>=arr.size()) return NULL;
        if(arr[ind].second==depth)
        {
            TreeNode *temp= new TreeNode(arr[ind].first);

            temp->left= go_deep(arr, ind+1, depth+1);
            temp->right = go_deep(arr, ind+1, depth+1);
            return temp;
        }
        return NULL;
    }


    TreeNode* recoverFromPreorder(string S) {

        int n=S.length();
        int depth=0;
        string ss="";
        int i;
        int j;
        int x=0;
        map<int,int> height;

        pair<int, int> PAIR1;
        vector<pair<int,int>> container;



        for(i=0;i<n;i++)
        {
            if(S[i]!='-')
            {   ss="";
                for(j=i;j<n;j++)
                {
                    if(S[j]!='-')
                    {
                       ss+=S[j];
                    }
                    else{
                        i=j-1;
                        break;
                    }
                }
                i=j-1;
               // cout<<ss<<"-> "<<depth<<endl;
                stringstream conv(ss);
                x=0;
                conv >> x;
                PAIR1.first=x;
                PAIR1.second=depth;
                container.push_back(PAIR1);
                ss="";
                depth=0;
            }
            else{
                depth++;
            }
        }


        for(auto x:container)
        {
            cout<<x.first<<", "<<x.second<<endl;

        }

        return go_deep(container,0,0);

    }
};