我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {

    private int index;

    private String traversal;

    private int getHeight() {
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < traversal.length(); ++i) {
            if (traversal.charAt(i) == '-') {
                sum++;
            } else {
                sum = 0;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }

    private int[] parse() {
        int level = 0;
        while (index < traversal.length() && traversal.charAt(index) == '-') {
            level++;
            index++;
        }
        int num = 0;
        while (index < traversal.length() && Character.isDigit(traversal.charAt(index))) {
            num = num * 10 + traversal.charAt(index++) - '0';
        }
        return new int[]{level, num};
    }

    public TreeNode recoverFromPreorder(String traversal) {
        if (traversal == null || traversal.length() == 0) {
            return null;
        }
        this.index = 0;
        this.traversal = traversal;
        TreeNode[] stack = new TreeNode[getHeight() + 1];
        TreeNode root = new TreeNode(parse()[1]);
        stack[0] = root;
        while (index < traversal.length()) {
            int[] node = parse();
            TreeNode parent = stack[node[0] - 1];
            TreeNode cur = new TreeNode(node[1]);
            stack[node[0]] = cur;
            if (parent.left == null) {
                parent.left = cur;
            } else {
                parent.right = cur;
            }
        }
        return root;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}