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

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

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

根节点的深度为 0

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

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

输入：“1-2–3--4-5–6--7”。

输出：[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完整代码如下：

package main

import (
	"fmt"
	"strconv"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

const MAXN = 2001

var queue [MAXN]int
var l, r int

func recoverFromPreorder(traversal string) *TreeNode {
    l = 0
    r = 0
    number := 0
    level := 0
    pickLevel := true
    for i := 0; i < len(traversal); i++ {
        c := traversal[i]
        if c != '-' {
            if pickLevel {
                queue[r] = level
                level = 0
                r++
                pickLevel = false
            }
            d, _ := strconv.Atoi(string(c))
            number = number*10 + d
        } else {
            if !pickLevel {
                queue[r] = number
                number = 0
                r++
                pickLevel = true
            }
            level++
        }
    }
    queue[r] = number
    return f()
}

func f() *TreeNode {
    level := queue[l]
    head := &TreeNode{Val: queue[l+1], Left: nil, Right: nil}
    l += 2
    if l < r && queue[l] > level {
        head.Left = f()
    }
    if l < r && queue[l] > level {
        head.Right = f()
    }
    return head
}

func main() {
    traversal := "1-2--3--4-5--6--7"
    result := recoverFromPreorder(traversal)
    fmt.Printf("%+v\n", result)
}

rust完整代码如下：

use std::cell::RefCell;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

fn recover_from_preorder(traversal: String) -> Option<Rc<RefCell<TreeNode>>> {
    let mut queue = vec![0; 2001];
    let mut l = 0;
    let mut r = 0;
    let mut number = 0;
    let mut level = 0;
    let mut pick_level = true;
    for c in traversal.chars() {
        if c != '-' {
            if pick_level {
                queue[r] = level;
                level = 0;
                r += 1;
                pick_level = false;
            }
            number = number * 10 + c.to_digit(10).unwrap() as i32;
        } else {
            if !pick_level {
                queue[r] = number;
                number = 0;
                r += 1;
                pick_level = true;
            }
            level += 1;
        }
    }
    queue[r] = number;
    let queue_len = r + 1;
    f(&mut queue, &mut l, queue_len, 0)
}

fn f(queue: &mut [i32], l: &mut usize, r: usize, level: i32) -> Option<Rc<RefCell<TreeNode>>> {
    if *l >= r || queue[*l] != level {
        None
    } else {
        *l += 1;
        let head = Rc::new(RefCell::new(TreeNode::new(queue[*l])));
        *l += 1;
        head.borrow_mut().left = f(queue, l, r, level + 1);
        head.borrow_mut().right = f(queue, l, r, level + 1);
        Some(head)
    }
}

fn main() {
    let traversal = String::from("1-2--3--4-5--6--7");
    let result = recover_from_preorder(traversal);
    println!("{:#?}", result);
}

c++完整代码如下：

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* f();

const int MAXN = 2001;
int queue[MAXN];
int l, r;

TreeNode* recoverFromPreorder(string traversal) {
    l = 0;
    r = 0;
    int number = 0;
    int level = 0;
    bool pickLevel = true;
    for (int i = 0; i < traversal.size(); i++) {
        char c = traversal[i];
        if (c != '-') {
            if (pickLevel) {
                queue[r++] = level;
                level = 0;
                pickLevel = false;
            }
            number = number * 10 + c - '0';
        }
        else {
            if (!pickLevel) {
                queue[r++] = number;
                number = 0;
                pickLevel = true;
            }
            level++;
        }
    }
    queue[r++] = number;
    return f();
}

TreeNode* f() {
    int level = queue[l++];
    TreeNode* head = new TreeNode(queue[l++]);
    if (l < r && queue[l] > level) {
        head->left = f();
    }
    if (l < r && queue[l] > level) {
        head->right = f();
    }
    return head;
}

int main() {
    string traversal = "1-2--3--4-5--6--7";
    TreeNode* result = recoverFromPreorder(traversal);
    cout << result->val << endl;
    cout << result->left->val << endl;
    cout << result->right->val << endl;
    cout << result->left->left->val << endl;
    cout << result->left->right->val << endl;
    cout << result->right->left->val << endl;
    cout << result->right->right->val << endl;
    return 0;
}

c语言完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* f();

#define MAXN 2001

int queue[MAXN];
int l, r;

struct TreeNode* recoverFromPreorder(char* traversal) {
    l = 0;
    r = 0;
    int number = 0;
    int level = 0;
    int pickLevel = 1;
    int len = strlen(traversal);
    for (int i = 0; i < len; i++) {
        char c = traversal[i];
        if (c != '-') {
            if (pickLevel) {
                queue[r++] = level;
                level = 0;
                pickLevel = 0;
            }
            number = number * 10 + c - '0';
        }
        else {
            if (!pickLevel) {
                queue[r++] = number;
                number = 0;
                pickLevel = 1;
            }
            level++;
        }
    }
    queue[r++] = number;
    return f();
}

struct TreeNode* f() {
    int level = queue[l++];
    struct TreeNode* head = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    head->val = queue[l++];
    head->left = NULL;
    head->right = NULL;
    if (l < r && queue[l] > level) {
        head->left = f();
    }
    if (l < r && queue[l] > level) {
        head->right = f();
    }
    return head;
}

int main() {
    char traversal[] = "1-2--3--4-5--6--7";
    struct TreeNode* result = recoverFromPreorder(traversal);
    printf("%d\n", result->val);
    printf("%d\n", result->left->val);
    printf("%d\n", result->right->val);
    printf("%d\n", result->left->left->val);
    printf("%d\n", result->left->right->val);
    printf("%d\n", result->right->left->val);
    printf("%d\n", result->right->right->val);
    return 0;
}