Recover a Tree From Preorder Traversal

class Solution {
public:
    TreeNode* recoverFromPreorder(string traversal) {
        vector<TreeNode*> stack;
        int i = 0, n = traversal.size();
        while (i < n) {
            int depth = 0;
            while (i < n && traversal[i] == '-') { ++depth; ++i; }
            int val = 0;
            while (i < n && isdigit(traversal[i])) {
                val = val * 10 + (traversal[i] - '0');
                ++i;
            }
            TreeNode* node = new TreeNode(val);
            while ((int)stack.size() > depth) stack.pop_back();
            if (!stack.empty()) {
                if (!stack.back()->left) stack.back()->left = node;
                else stack.back()->right = node;
            }
            stack.push_back(node);
        }
        return stack.front();
    }
};

func recoverFromPreorder(traversal string) *TreeNode {
    stack := []*TreeNode{}
    i, n := 0, len(traversal)
    for i < n {
        depth := 0
        for i < n && traversal[i] == '-' {
            depth++
            i++
        }
        val := 0
        for i < n && traversal[i] >= '0' && traversal[i] <= '9' {
            val = val*10 + int(traversal[i]-'0')
            i++
        }
        node := &TreeNode{Val: val}
        for len(stack) > depth {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            top := stack[len(stack)-1]
            if top.Left == nil {
                top.Left = node
            } else {
                top.Right = node
            }
        }
        stack = append(stack, node)
    }
    return stack[0]
}

from typing import List, Optional

class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        stack: List[TreeNode] = []
        i, n = 0, len(traversal)
        while i < n:
            depth = 0
            while i < n and traversal[i] == '-':
                depth += 1
                i += 1
            val = 0
            while i < n and traversal[i].isdigit():
                val = val * 10 + int(traversal[i])
                i += 1
            node = TreeNode(val)
            while len(stack) > depth:
                stack.pop()
            if stack:
                top = stack[-1]
                if top.left is None:
                    top.left = node
                else:
                    top.right = node
            stack.append(node)
        return stack[0]

function recoverFromPreorder(traversal) {
    const stack = [];
    let i = 0, n = traversal.length;
    while (i < n) {
        let depth = 0;
        while (i < n && traversal[i] === '-') { depth++; i++; }
        let val = 0;
        while (i < n && traversal[i] >= '0' && traversal[i] <= '9') {
            val = val * 10 + (traversal.charCodeAt(i) - 48);
            i++;
        }
        const node = new TreeNode(val);
        while (stack.length > depth) stack.pop();
        if (stack.length > 0) {
            const top = stack[stack.length - 1];
            if (top.left === null) top.left = node;
            else top.right = node;
        }
        stack.push(node);
    }
    return stack[0];
}

class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        int i = 0, n = traversal.length();
        while (i < n) {
            int depth = 0;
            while (i < n && traversal.charAt(i) == '-') { depth++; i++; }
            int val = 0;
            while (i < n && Character.isDigit(traversal.charAt(i))) {
                val = val * 10 + (traversal.charAt(i) - '0');
                i++;
            }
            TreeNode node = new TreeNode(val);
            while (stack.size() > depth) stack.pop();
            if (!stack.isEmpty()) {
                TreeNode top = stack.peek();
                if (top.left == null) top.left = node;
                else top.right = node;
            }
            stack.push(node);
        }
        return stack.peekLast();
    }
}

function recoverFromPreorder(traversal: string): TreeNode | null {
    const stack: TreeNode[] = [];
    let i = 0;
    const n = traversal.length;
    while (i < n) {
        let depth = 0;
        while (i < n && traversal[i] === '-') { depth++; i++; }
        let val = 0;
        while (i < n && traversal[i] >= '0' && traversal[i] <= '9') {
            val = val * 10 + (traversal.charCodeAt(i) - 48);
            i++;
        }
        const node = new TreeNode(val);
        while (stack.length > depth) stack.pop();
        if (stack.length > 0) {
            const top = stack[stack.length - 1];
            if (top.left === null) top.left = node;
            else top.right = node;
        }
        stack.push(node);
    }
    return stack[0];
}