2023年6月22日发(作者：)

题目:从先序遍历还原二叉树

我们从二叉树的根节点

root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出

D 条短划线（其中

D 是该节点的深度），然后输出该节点的值。（如果节点的深度为

D，则其直接子节点的深度为

D + 1。根节点的深度为

0）。

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

给出遍历输出

S，还原树并返回其根节点

root。

示例 1：

输入："1-2--3--4-5--6--7"

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

示例 2： 输入："1-2--3---4-5--6---7"

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

示例 3：

输入："1-401--349---90--88"

输出：[1,401,null,349,88,90]

提示：

•

•

原始树中的节点数介于

1 和

1000 之间。

每个节点的值介于

1 和

10 ^ 9 之间。

语言:C++

class Solution {

public:

TreeNode* recoverFromPreorder(string traversal) {

stack path;

int pos = 0;

while (pos < ()) {

int level = 0;

while (traversal[pos] == '-') {

++level;

++pos;

}

int value = 0;

while (pos < () && isdigit(traversal[pos])) {

value = value * 10 + (traversal[pos] - '0');

++pos;

}

TreeNode* node = new TreeNode(value);

if (level == ()) {

if (!()) {

()->left = node;

}

}

else {

while (level != ()) {

();

}

()->right = node;

}

(node);

}

while (() > 1) {

();

}

return ();

}

};

语言:Java

class Solution {

public TreeNode recoverFromPreorder(String traversal) {

Deque path = new LinkedList();

int pos = 0; while (pos < ()) {

int level = 0;

while ((pos) == '-') {

++level;

++pos;

}

int value = 0;

while (pos < () && t((pos))) {

value = value * 10 + ((pos) - '0');

++pos;

}

TreeNode node = new TreeNode(value);

if (level == ()) {

if (!y()) {

().left = node;

}

} else {

while (level != ()) {

();

}

().right = node;

}

(node);

}

while (() > 1) {

();

}

return ();

}

}

语言:Python

class Solution:

def recoverFromPreorder(self, traversal: str) -> TreeNode:

path, pos = list(), 0

while pos < len(traversal):

level = 0

while traversal[pos] == '-':

level += 1

pos += 1

value = 0

while pos < len(traversal) and traversal[pos].isdigit():

value = value * 10 + (ord(traversal[pos]) - ord('0'))

pos += 1

node = TreeNode(value)

if level == len(path):

if path:

path[-1].left = node

else:

path = path[:level]

path[-1].right = node

(node)

return path[0] 语言:golang

func recoverFromPreorder(traversal string) *TreeNode {

path, pos := []*TreeNode{}, 0

for pos < len(traversal) {

level := 0

for traversal[pos] == '-' {

level++

pos++

}

value := 0

for ; pos < len(traversal) && traversal[pos] >= '0' && traversal[pos] <= '9'; pos++ {

value = value * 10 + int(traversal[pos] - '0')

}

node := &TreeNode{Val: value}

if level == len(path) {

if len(path) > 0 { path[len(path)-1].Left = node }

} else {

path = path[:level]

path[len(path)-1].Right = node

}

path = append(path, node)

}

return path[0]

}

语言:js

const recoverFromPreorder = (s) => {

const stack = []; //

维护一个栈

for (let i = 0; i < ; ) {

let curLevel = 0; //

当前构建的节点所属的level

while (i < && s[i] == '-') { //

数数有几个连字符

curLevel++; //

统计它的level

i++; //

扫描的指针+1

}

let start = i; //

记录下节点值字符串的开始位置

while (i < && s[i] != '-') { //

扫描节点值字符串

i++; //

扫描的指针+1

} const val = ing(start, i); //

截取出节点值

const curNode = new TreeNode(val); //

创建节点

if ( == 0) { //

此时栈为空，curNode为根节点

(curNode); //

入栈，成为栈底

continue; //

它没有父亲，不用找父亲，continue

}

while ( > curLevel) {//

只要栈高>当前节点的level，就栈顶出栈

();

}

if (stack[ - 1].left) { //

栈顶是父亲了，但左儿子已经存在

stack[ - 1].right = curNode; // curNode成为右儿子

} else {

stack[ - 1].left = curNode; //

否则，成为左儿子

}

(curNode); // curNode自己也是父亲，入栈，等儿子

}

return stack[0]; //

栈底节点肯定是根节点

};

语言:js

const recoverFromPreorder = (S) => {

let index = 0 //

遍历字符串的指针

const buildTree = (S, level) => { //

构建当前子树，它属于第level层

let curLevel = 0 //

当前遇到的节点的level

while (index < && S[index] == '-') {

curLevel++ //

计算curNode的level

index++ //

指针步进，+1

}

if (curLevel < level) { //

我们想要构建第level层的一个子树，但遇到的当前节点的curLevel

//

却不等于level(比level小)，说明该子树已经构建完毕，要出递归栈（结束递归）

index -= curLevel //

刚刚的while循环，index已经前进了curLevel长度，要退回来

return null //

递归的出口，返回null节点

}

let start = index //

记录节点值开头的位置

while (index < && S[index] != '-') {

index++ //

指针随着节点值推进

}

let val = (start, index) //

截取出节点值

let curNode = new TreeNode(val) //

创建当前节点

= buildTree(S, level + 1) //

构建当前节点的左子树

= buildTree(S, level + 1) //

构建当前节点的右子树

return curNode //

返回子树

}

return buildTree(S, 0) //

构建第0层的子树，即整个树

};

语言:php

class Solution

{

/**

* @param String $S

* @return TreeNode

*/

function recoverFromPreorder($S)

{

$len = strlen($S); $stack = [];

for ($i = 0; $i < $len;) {

//

先记录当前节点的 level

$curLevel = 0;

while ($i < $len && $S[$i] == '-') {

$i++;

$curLevel++;

}

//

当前节点的开始位置

$start = $i;

while ($i < $len && $S[$i] != '-') {

//

指针移到当前节点的结束位置

$i++;

}

$curNode = new TreeNode(substr($S, $start, $i - $start));

//

根节点入栈

if (count($stack) == 0) {

$stack[] = $curNode;

continue;

}

//

栈顶不是父亲，出栈

while (count($stack) > $curLevel) {

array_pop($stack);

}

//

左子节点已存在，安排为右儿子

if (end($stack)->left) {

end($stack)->right = $curNode;

} else {

end($stack)->left = $curNode;

}

$stack[] = $curNode;

}

return $stack[0];

}

}