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



```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2025/536.-construct-binary-tree-from-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.