- 标签:树、深度优先搜索、字符串、二叉树
- 难度:困难
题目大意
#
对一棵二叉树进行深度优先搜索。在遍历的过程中,遇到节点,先输出与该节点深度相同数量的短线,再输出该节点的值。如果节点深度为 D
,则子节点深度为 D + 1
。根节点的深度为 0
。如果节点只有一个子节点,则该子节点一定为左子节点。
现在给定深度优先搜索输出的字符串 traversal
。
要求:还原二叉树,并返回其根节点 root
。
解题思路
#
用栈存储需要构建子树的节点。并记录下上一节点深度和当前节点深度。
然后遍历深度优先搜索的输出字符串。
代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
class Solution:
def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
stack = []
index, num = 0, 0
pre_level, cur_level = 0, 0
size = len(traversal)
while index < size and traversal[index] != '-':
num = num * 10 + ord(traversal[index]) - ord('0')
index += 1
root = TreeNode(num)
stack.append(root)
while index < size:
if traversal[index] == '-':
cur_level += 1
index += 1
else:
num = 0
while index < size and traversal[index] != '-':
num = num * 10 + ord(traversal[index]) - ord('0')
index += 1
if cur_level > pre_level:
node = stack.pop()
node.left = TreeNode(num)
stack.append(node)
stack.append(node.left)
pre_level = cur_level
cur_level = 0
else:
while len(stack) > cur_level:
stack.pop()
node = stack.pop()
node.right = TreeNode(num)
stack.append(node)
stack.append(node.right)
pre_level = cur_level
cur_level = 0
return root
|