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;
}