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 * 104

• s consists of digits, '(', ')', and '-' only.

• All numbers in the tree have value at most than 230.

分析

问题描述

给定一个字符串 s，表示一棵二叉树的 前序遍历 序列化形式，要求将其还原为一棵二叉树。字符串的格式规则如下：

• 节点值可能为 负数 或 多位数。

• 如果节点有子节点，则用 (左子树)(右子树) 表示；如果没有子节点，则省略括号。

1. 找到根节点值：

   • 从当前字符开始，读取所有连续的数字（包括符号），解析为 root.val。

2. 处理左子树：

   • 如果遇到 (，递归构建左子树。

3. 处理右子树：

   • 如果左子树处理完后还有 (，递归构建右子树。

4. 终止条件：

   • 遇到 ) 或字符串结束，返回当前节点。

# 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]