Recover a Tree From Preorder Traversal

We run a preorder depth first search 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. (If the depth of a node is D, the depth of its immediate child is D+1. 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 S of this traversal, recover the tree and return its root.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

• The number of nodes in the original tree is between 1 and 1000.

• Each node will have a value between 1 and 10^9.

class Solution {
    public TreeNode helper(String s, int start, int end) {
        if (start > end)
            return null;
        StringBuilder number = new StringBuilder();
        while (start <= end && s.charAt(start) >= '0' && s.charAt(start) <= '9')
            number.append(s.charAt(start++));
        int val = Integer.parseInt(number.toString());
        TreeNode root = new TreeNode(val);
        if (start > end)
            return root;
        int len = 0;
        int rightindex = -1;
        while (start <= end && s.charAt(start) == '-') {
            start++;
            len++;
        }
        for (int i = start; i <= end; i++) {
            int lenDashes = 0;
            boolean dash = false;
            while (i <= end && s.charAt(i) == '-') {
                i++;
                lenDashes++;
                dash = true;
            }
            if (dash && lenDashes == len) {
                rightindex = i - lenDashes;
                i--;
                break;
            }
        }
        if (rightindex == -1)
            root.left = helper(s, start, end);
        else {
            root.left = helper(s, start, rightindex - 1);
            root.right = helper(s, rightindex + len, end);
        }
        return root;
    }

    public TreeNode recoverFromPreorder(String S) {
        return helper(S, 0, S.length() - 1);
    }
}