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

# 0536. Construct Binary Tree from String

<https://leetcode.com/problems/construct-binary-tree-from-string>

## Description

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)

```
**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.

## ac

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int i = 0;

    public TreeNode str2tree(String s) {
        TreeNode root = null;

        int p = i;
        while (i < s.length() && s.charAt(i) != '(' && s.charAt(i) != ')') i++; // get root value
        String tmp = s.substring(p, i);
        if (tmp.length() != 0) { // some empty value like "()"
            int val = Integer.parseInt(tmp);
            root = new TreeNode(val);
        }

        if (i < s.length() && s.charAt(i++) == '(') { // '(' means the start of a child node, careful about boundary
            root.left = str2tree(s);

            if (i < s.length() && s.charAt(i++) == '(') {
                root.right = str2tree(s);
                i++; // when right child finish (not leaf), it's always like "))"
            }
        }

        return root;
    }
}

/*
regard string as a queue, similar to #297 queue deserialize
*/
```