We run a&nbsp;preorder&nbsp;depth-first search (DFS) on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node.&nbsp; If the depth of a node is D, the depth of its immediate child is D + 1.&nbsp; The depth of the root node is 0.

If a node has only one child, that child is guaranteed to be the left child.

Given the output traversal of this traversal, recover the tree and return its root.

&nbsp;
Example 1:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]


Example 2:

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]


Example 3:

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]


&nbsp;
Constraints:


	The number of nodes in the original tree is in the range [1, 1000].
	1 &lt;= Node.val &lt;= 109


class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        i = 0
        dummy_head = TreeNode()
        depth = 0
        while i < len(traversal):
            if traversal[i].isdigit():
                value, i = get_value(traversal, i)
                insert_node(dummy_head, depth, value)

            else:
                depth, i = get_depth(traversal, i)

        return dummy_head.left

# Returns the next value from the string traversal, and returns the position following the last digit of the current value.
def get_value(traversal, i):
    value = 0
    while i < len(traversal) and traversal[i].isdigit():
        value *= 10
        value += int(traversal[i])
        i += 1

    return value, i

# Insertes a node of the given `value` at the given `depth` of the subtree whose root is the given `root`.
def insert_node(root, depth, value):
    for _ in range(depth):
        if root.right:
            root = root.right
        else:
            root = root.left

    new_node = TreeNode(value)
    if root.left:
        root.right = new_node
    else:
        root.left = new_node

# Gets the next depth from the string traversal, and returns the position following the last dash of the current depth.
def get_depth(traversal, i):
    depth = 0
    while i < len(traversal) and traversal[i] == "-":
        depth += 1
        i += 1

    return depth, i
class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        if(!traversal.contains("-"))
            return new TreeNode(Integer.parseInt(traversal));
        String number = "";
        int i = 0;
        while(traversal.charAt(i)!='-'){
            number+=traversal.charAt(i);
            i++;
        }
        //System.out.print("root = " + number + " " + i + "     ");
        TreeNode root = new TreeNode(Integer.parseInt(number));
        StringBuilder str = new StringBuilder();
        int bk = 0;
        for(int j = i; i < traversal.length(); i++){
            if(traversal.charAt(i-1) != '-' && traversal.charAt(i) == '-' && traversal.charAt(i+1) != '-')
                bk = str.toString().length();
            else if(!(traversal.charAt(i-1) != '-' && traversal.charAt(i) == '-'))
                str.append(traversal.charAt(i));
        }
        String divide = str.toString();
        
        TreeNode left = (bk==0)?recoverFromPreorder(divide):recoverFromPreorder(divide.substring(0,bk));
        TreeNode right = (bk==0)?null:recoverFromPreorder(divide.substring(bk,divide.length()));
        root.left = left;
        root.right = right;
            
        
        return root;
    }
}
class Solution {
public:

    // Returns the index of '-' if present otherwise returns the string length
    int findIndex(int ind, string &traversal){
        int req = traversal.size();
        for(int i=ind; i<traversal.size(); i++){
            if(traversal[i] == '-'){
                req = i;
                break;
            }
        }
        return req;
    }

    TreeNode* recoverFromPreorder(string traversal) {
        // Pushing the node along with its depth into the stack
        int depth = 0;
        stack<pair<TreeNode*,int>> st;

        // Finding the root node
        int ind = findIndex(0, traversal);
        string str = traversal.substr(0, ind);
        TreeNode *root = new TreeNode(stoi(str));

        // Pushing the root node along with its depth
        st.push({root, 0});

        // Starting from 'ind' as it has the next '-' character
        int i = ind;

        while(i<traversal.size()){
            // Increment the depth
            if(traversal[i] == '-'){
                depth++;
                i++;
                continue;
            }

            // Find the complete number as no.of digits can be > 1
            int ind = findIndex(i, traversal);
            string str = traversal.substr(i, ind-i);
            TreeNode *node = new TreeNode(stoi(str));

            // Finding its appropriate parent, whose depth is one less than current depth
            while(!st.empty() && st.top().second != depth-1){
                st.pop();
            }

            // There is already left child for the parent
            if(st.top().first->left){
                st.top().first->right = node;
            }
            else{
                st.top().first->left = node;
            }

            // Pushing that node and its depth into stack
            st.push({node, depth});
            depth = 0;
            i = ind;
        }

        return root;
    }
};
var recoverFromPreorder = function(traversal) {
    
    let n = traversal.length;
    
    // Every layer in dfs handles the depth+1 of '-' only.
    // ex: 
    //   depth=0 -> find '-'  as splitter
    //   depth=1 -> find '--' as splitter
    //   depth=2 -> find '---' as splitter
    let dfs = (str,depth)=>{
        if(str.indexOf("-") === -1) return new TreeNode(str);
		
		// 1. We split by the depth+1 number of '-'
        // Using regex to split is much easier. -> str.split(/(?<=\d)-(?=\d)/g)
		// where (?<=\d)  means positive lookbehind , ex: "1- ...", then we'll split '-' excluding 1.
		// Similarly , (?=\d) means positive lookahead , ex: "-5 ...",  then we'll split '-' excluding 5.
		
        let re = new RegExp(`(?<=\\d)${"-".repeat(depth+1)}(?=\\d)`,'g');
        let [val,leftStr,rightStr] = str.split(re);
        // ex: 1-2--3--4-5--6--7 --> ['1','2--3--4','5--6--7']
        
		// 2. After splitting,  we'll get [val,leftStr,rightStr]
		// Then we could handle left / right node in the next dfs layer intuitively.
        let node = new TreeNode(val);
        if(leftStr)  node.left  = dfs(leftStr,depth+1);
        if(rightStr) node.right = dfs(rightStr,depth+1);
        
        return node;
    };
    
    return dfs(traversal,0);
    
};
Recover a Tree From Preorder Traversal