LeetCode 1028 - Recover a Tree From Preorder Traversal

https://leetcode.com/problems/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

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/discuss/274656/Java-recursive-solution.

    int index = 0;
    public TreeNode recoverFromPreorder(String S) {
        return helper(S, 0);
    }
    
    public TreeNode helper(String s, int depth) {
        int numDash = 0;
        while (index + numDash < s.length() && s.charAt(index + numDash) == '-') {
            numDash++;
        }
        if (numDash != depth) return null;
        int next = index + numDash;
        while (next < s.length() && s.charAt(next) != '-') next++;
        int val = Integer.parseInt(s.substring(index + numDash, next));
        index = next;
        TreeNode root = new TreeNode(val);
        root.left = helper(s, depth + 1);
        root.right = helper(s, depth + 1);
        return root;
    }

https://zxi.mytechroad.com/blog/leetcode/leetcode-weekly-contest-132/

  TreeNode* recoverFromPreorder(string S) {

    int i = 0;

    return recover(S, i, 0);

  }

private:

  TreeNode* recover(const string& s, int& i, int depth) {    

    const int d = getD(s, i);

    if (d != depth) { i -= d; return nullptr; }    

    auto root = new TreeNode(getVal(s, i));

    root->left = recover(s, i, d + 1);    

    root->right = recover(s, i, d + 1);

    return root;

  }

  

  int getD(const string& s, int& i) {

    int d = 0;

    while (i < s.length() && s[i] == '-') {++d; ++i;}

    return d;

  }

  

  int getVal(const string& s, int& i) {

    int val = 0;

    while (i < s.length() && isdigit(s[i]))

      val = val * 10 + (s[i++] - '0');      

    return val;

  }