1028. 从先序遍历还原二叉树 python 100%内存 一次遍历
题目
我们从二叉树的根节点 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 之间。
解题思路
在for循环字符串的过程中 使用了 4个变量 returnlist 作为栈容器 index作为当前位置索引 , level作为当前节点层级,val记录当前node的值 (注意要凑出当val 不为10以内的情况时 使用10进制的拼接来做 val )
一次遍历得出最终树的head
代码
```python3
class Solution:
def recoverFromPreorder(self, S: str) -> TreeNode:
returnlist = [] #returnlist 作为栈容器
index = 0 #index作为当前位置索引
level = 0 # level作为当前节点层级
val = 0 # val记录当前node的值 (注意当val>10的情况时 使用10进制的拼接来得出真实val )
for i in S:
if i == "-": # 判断当前位置
index += 1
level += 1
else:
index += 1
if index<len(S) and S[index].isdigit(): # 判断当前的i 对象下一个是否也是数字 ,是就进行拼接,并跳过当前循环 ,保持住当前level 不变
val = int(i) + val*10
continue
val = int(i) + val*10 #总能得到真实val的值
node = TreeNode(val) #生成node节点对象 ----
val = 0
if level == 0: #首节点
returnlist.append(node)
else: #非首节点
if level == len(returnlist): #根据题意 只能 树的左分支有值 所以 直接判断 当前层级与树层级 将最左边的树的那一分支 先构建出来
returnlist[-1].left = node
else:
returnlist = returnlist[:level] #所有不是最左分支的节点 根据自己的层级 做判断 取出当前栈中 所属层级的最后一位 (因为题目是二叉树所以这样取没问题,如果非二叉树就复杂了)
returnlist[-1].right = node
returnlist.append(node) # 节点入栈
level = 0 #入栈后重新开始 level 计数
# print('val >>',val,'i >>',i,'level >>', level,'len >>'len(returnlist), returnlist) #打印结果如下示例
return returnlist[0]
### 案例1的打印情况 方便理解具体栈内部情况
# print('val >>',val,'i >>',i,'level >>', level,'len >>'len(returnlist), returnlist) #打印结果如下示例
输入值为"1-2--3--4-5--6--7" 输入值 字符串 S为 目的是还原为 如下树结构
输出：head 广度优先 表示为 >> [1,2,5,3,4,6,7]
val> 0 i> 1 level> 0 len> 1 [TreeNode{val: 1, left: None, right: None}]
val> 0 i> 2 level> 0 len> 2 [TreeNode{val: 1, left: TreeNode{val: 2, left: None, right: None}, right: None}, TreeNode{val: 2, left: None, right: None}]
val> 0 i> 3 level> 0 len> 3 [TreeNode{val: 1, left: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: None}, right: None}, TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: None}, TreeNode{val: 3, left: None, right: None}]
val> 0 i> 4 level> 0 len> 3 [TreeNode{val: 1, left: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 4, left: None, right: None}}, right: None}, TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 4, left: None, right: None}}, TreeNode{val: 4, left: None, right: None}]
val> 0 i> 5 level> 0 len> 2 [TreeNode{val: 1, left: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 4, left: None, right: None}}, right: TreeNode{val: 5, left: None, right: None}}, TreeNode{val: 5, left: None, right: None}]
val> 0 i> 6 level> 0 len> 3 [TreeNode{val: 1, left: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 4, left: None, right: None}}, right: TreeNode{val: 5, left: TreeNode{val: 6, left: None, right: None}, right: None}}, TreeNode{val: 5, left: TreeNode{val: 6, left: None, right: None}, right: None}, TreeNode{val: 6, left: None, right: None}]
val> 0 i> 7 level> 0 len> 3 [TreeNode{val: 1, left: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 4, left: None, right: None}}, right: TreeNode{val: 5, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}}, TreeNode{val: 5, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}, TreeNode{val: 7, left: None, right: None}]