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 level {
head.Left = f()
}
if l level {
head.Right = f()
}
return head
}
func main() {
traversal := "1-2--3--4-5--6--7"
result := recoverFromPreorder(traversal)
fmt.Printf("%+vn", result)
}
rust完整代码如下:
use std::cell::RefCell;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option>>,
pub right: Option>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
fn recover_from_preorder(traversal: String) -> Option>> {
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>> {
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
#include
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 level) {
head->left = f();
}
if (l level) {
head->right = f();
}
return head;
}
int main() {
string traversal = "1-2--3--4-5--6--7";
TreeNode* result = recoverFromPreorder(traversal);
cout val left->val right->val left->left->val left->right->val right->left->val right->right->val
c语言完整代码如下:
#include
#include
#include
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 val = queue[l++];
head->left = NULL;
head->right = NULL;
if (l level) {
head->left = f();
}
if (l level) {
head->right = f();
}
return head;
}
int main() {
char traversal[] = "1-2--3--4-5--6--7";
struct TreeNode* result = recoverFromPreorder(traversal);
printf("%dn", result->val);
printf("%dn", result->left->val);
printf("%dn", result->right->val);
printf("%dn", result->left->left->val);
printf("%dn", result->left->right->val);
printf("%dn", result->right->left->val);
printf("%dn", result->right->right->val);
return 0;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
作者:良知犹存 转载授权以及围观:欢迎关注微信公众号:羽林君 或者添加作者个人微信:become_me 扫地机介绍 扫地机器人行业本质是技术驱动型行业,产品围绕导航系统的升级成为行业发展的主旋律。按功能划分,扫地机器人分为四大系统,即导航系统、清洁系统、续航…