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]


Last updated

Was this helpful?