> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/536.-construct-binary-tree-from-string.md).

# 536. Construct Binary Tree from String

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

![](https://assets.leetcode.com/uploads/2020/09/02/butree.jpg)

<pre><code><strong>Input: s = "4(2(3)(1))(6(5))"
</strong><strong>Output: [4,2,6,3,1,5]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "4(2(3)(1))(6(5)(7))"
</strong><strong>Output: [4,2,6,3,1,5,7]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: s = "-4(2(3)(1))(6(5)(7))"
</strong><strong>Output: [-4,2,6,3,1,5,7]
</strong></code></pre>

**Constraints:**

* `0 <= s.length <= 3 * 10`<sup>`4`</sup>
* `s` consists of digits, `'('`, `')'`, and `'-'` only.
* All numbers in the tree have value **at most** than `2`<sup>`30`</sup>.

分析

**问题描述**

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

* 节点值可能为 **负数** 或 **多位数**。
* 如果节点有子节点，则用 `(左子树)(右子树)` 表示；如果没有子节点，则省略括号。

1. **找到根节点值**：
   * 从当前字符开始，读取所有连续的数字（包括符号），解析为 `root.val`。
2. **处理左子树**：
   * 如果遇到 `(`，递归构建左子树。
3. **处理右子树**：
   * 如果左子树处理完后还有 `(`，递归构建右子树。
4. **终止条件**：
   * 遇到 `)` 或字符串结束，返回当前节点。

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



```