1028. Recover a Tree From Preord

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.
Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
这题我喜欢用recursion写 代码简洁
如何判断一个节点有没有左孩子，只要看它的下一个节点的深度是不是当前的深度加1。
当前的深度，可以由--的长度算出。
如果--的个数不match，则这个节点不是上一个节点的孩子。
用preorder traversal做一下就好了。
其实比较routine

class Solution {
    public TreeNode recoverFromPreorder(String S) {
        int[] index = new int[]{-1};
        return helper(S, index, 0);
    }
    private TreeNode helper(String s, int[] index, int depth) {
        int fast = index[0];
        if (fast + 1 >= s.length()) return null;
        while (fast + 1 < s.length() && s.charAt(fast + 1) == '-' ) fast++;
        int curDepth = fast - index[0];
        if (curDepth != depth) return null; //这是本题的关键， 如果深度不match， 则返回null。
        int n = 0;
        while (fast + 1 < s.length() && Character.isDigit(s.charAt(fast + 1))) {
            n *= 10;
            n += s.charAt(++fast) - '0';
        }
        TreeNode node = new TreeNode(n);
        index[0] = fast;
        node.left = helper(s, index, curDepth + 1);
        node.right = helper(s, index, curDepth + 1);
        return node;
    }
}