# LeetCode: 1028. 从先序遍历还原二叉树¶

## 1、题目描述¶

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



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



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



• 原始树中的节点数介于 1 和 1000 之间。
• 每个节点的值介于 1 和 10 ^ 9 之间。

## 2、解题思路¶

• 递归法
• 主要是分出根节点与左右子树的位置，然后不断递归
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def recoverFromPreorder(self, S: str) -> TreeNode:
if not S:
return None

current_dashes = 0

while S[current_dashes] == "-":
current_dashes += 1

root_nums = current_dashes

while root_nums < len(S) and S[root_nums] != "-":
root_nums += 1

node = TreeNode(int(S[current_dashes:root_nums]))

son_dashes = current_dashes + 1
left = root_nums
right = left + 1
while right < len(S):
if S[right] == "-" and S[right - 1] != "-" and S[right:right + son_dashes] == "-" * son_dashes and S[
right + son_dashes] != "-":
break
right += 1
node.left = self.recoverFromPreorder(S[left:right])
node.right = self.recoverFromPreorder(S[right:])
return node