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]intvar 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;}
复制代码
评论