题目：

https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/

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

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

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

给出遍历输出 S，还原树并返回其根节点 root。
case1：
输入：“1-2–3--4-5–6--7”
输出：[1,2,5,3,4,6,7]

思路

1. 本题给出一个二叉树先序遍历的结果，然后让根据先序遍历的结果还原二叉树
2. 采用递归的思想，S是先续遍历的结果，所以S中字符的顺序肯定是当前节点 + 左子树的遍历结果 + 右子树的遍历结果 ，首先根据S得到当前节点，然后递归调用函数，通过S构建左子树，然后再通过S构建右子树。
3. 类似于通过先续遍历结果构建二叉树的思想，核心思想是通过一个index下标进行S遍历位置的标记， 然后通过构建当前节点+ 递归调用的思想进行code。
4. 本题的变式在于对 在只有一个节点时一定是左节点的前提下，当前节点所处层级和 期望的层级进行比较， 只有当相同时才可以进行节点的构建，其他情况表示当前节点和当前位置不匹配，

code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

 /*
    根据先序遍历构造一个二叉树，  可以采用递归的思想，先根据S构造

    不对输入的特殊情况进行检查
 */
class