536. Construct Binary Tree from String
recursive, double return
You need to construct a binary tree from a string consisting of parenthesis and integers.
The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.
You always start to construct the left child node of the parent first if it exists.
Example 1:
Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]
Example 2:
Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]
Example 3:
Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]
Constraints:
0 <= s.length <= 3 * 10
4
s
consists of digits,'('
,')'
, and'-'
only.All numbers in the tree have value at most than
2
30
.
分析
问题描述
给定一个字符串 s
,表示一棵二叉树的 前序遍历 序列化形式,要求将其还原为一棵二叉树。字符串的格式规则如下:
节点值可能为 负数 或 多位数。
如果节点有子节点,则用
(左子树)(右子树)
表示;如果没有子节点,则省略括号。
找到根节点值:
从当前字符开始,读取所有连续的数字(包括符号),解析为
root.val
。
处理左子树:
如果遇到
(
,递归构建左子树。
处理右子树:
如果左子树处理完后还有
(
,递归构建右子树。
终止条件:
遇到
)
或字符串结束,返回当前节点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def str2tree(self, s: str) -> Optional[TreeNode]:
n = len(s)
def helper(s, index):
if index >= len(s) or s[index] == ')':
return None, index
sign = 1
if s[index] == '-':
sign = -1
index += 1
num = 0
while index < len(s) and s[index].isdigit():
num = num*10 + int(s[index])
index += 1
num = sign*num
root = TreeNode(num)
if index < n and s[index] == '(':
root.left, index = helper(s, index+1)
if root.left and index < n and s[index] == '(':
root.right, index = helper(s, index+1)
if index < len(s) and s[index] == ')':
index += 1
return root, index
if not s:
return None
return helper(s,0)[0]
Last updated
Was this helpful?