2023-06-14：我们从二叉树的根节点 root 开始进行深度优先搜索。在遍历中的每个节点处，我们输出 D 条短划线（其中

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

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度）

然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1

根节点的深度为 0

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

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

输出：[1,2,5,3,4,6,7]。

答案2023-06-14：

大体过程如下：

1.根据输入的遍历字符串 S 来构建一个二叉树。

2.定义一个结构体类型 TreeNode，表示二叉树的节点，包括节点值 Val，左子节点 Left，右子节点 Right。

3.定义一个数组 queue，用于存储节点的深度和值。

4.定义两个全局变量 l 和 r，表示队列的左右指针。

5.定义一个函数 recoverFromPreorder，用于根据遍历字符串 S 还原二叉树。

6.遍历字符串 S 的每一个字符：

a.如果该字符不为 '-'（即为数字字符），记录下该数字，直到该数字记录完毕。

b.如果该字符为 '-'，则表示该数字已经记录完毕，将该数字加入到 queue 数组中，并将 pickLevel 置为 true。

c.如果该字符是 '-' 或者到达字符串末尾，表示该数字已经记录完毕，将 lvel 记录到队列中， pickLevel 置为 false 。

d.如果该字符是 '-'，表示深度加 1；否则，将该数字加入到 number 中。

7.处理掉最后一个数字，将其加入到队列 queue 中。

8.定义一个递归函数 f，用于生成节点，并构建二叉树。

9.取出队列的第一个元素 level，它是当前节点的深度。

10.取出队列的第二个元素 val，它是当前节点的值。

11.生成一个 TreeNode 类型的结构体，元素值为 val，左子节点和右子节点置为 nil。

12.如果队列不为空，且队列的下一个元素的值大于当前节点深度 level，则递归进入左子节点，生成左子树。

13.同样，如果队列不为空，且队列的下一个元素的值大于当前节点深度 level，则递归进入右子节点，生成右子树。

14.返回根节点 head。

时间复杂度为 O(n)，其中 n 是遍历字符串 S 的长度。需要遍历字符串 S 一次，并将每个节点入队一次，然后根据队列中的节点数构建二叉树，构建二叉树的时间复杂度也是 O(n)。因此，总时间复杂度为 O(n)。

空间复杂度为 O(n)，需要一个数组来存储节点的深度和值，并将其入队。由于二叉树不一定是满二叉树，因此最多需要存储 2n 个节点的深度和值信息。因此，总空间复杂度为 O(n)。

go完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述c语言完整代码如下：

在这里插入图片描述