# 536     Construct Binary Tree from String

## 536. [Construct Binary Tree from String](https://leetcode.com/problems/construct-binary-tree-from-string/description/)

## 1. Question

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

```
Input: "4(2(3)(1))(6(5))"

Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5
```

**Note:**

1. There will only be`'('`,`')'`,`'-'`and`'0'`\~`'9'`in the input string.
2. An empty tree is represented by`""`instead of`"()"`.

## 2. Implementation

**(1) Recursion**

```java
class Solution {
    int i;
    public TreeNode str2tree(String s) {
        i = 0;
        return buildTree(s);
    }

    public TreeNode buildTree(String s) {
        StringBuilder num = new StringBuilder();

        while (i < s.length() && (s.charAt(i) == '-' || Character.isDigit(s.charAt(i)))) {
            num.append(s.charAt(i));
            i++;
        }

        if (num.length() == 0) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(num.toString()));

        // Left SubTree
        if (i < s.length() && s.charAt(i) == '(') {
            // Skip '('
            ++i;
            root.left = buildTree(s);
            // Skip ')'
            ++i;
        }

        // Right SubTree
        if (i < s.length() && s.charAt(i) == '(') {
            ++i;
            root.right = buildTree(s);
            ++i;
        }
        return root;
    }
}
```

**(2) Iteration**

```java
class Solution {
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();

        for (int end = 0, start = 0; end < s.length(); end++, start = end) {
            char c = s.charAt(end);

            if (c == '(') {
                continue;
            }
            else if (c == ')') {
                stack.pop();
            }
            else {
                while (end + 1< s.length() && Character.isDigit(s.charAt(end + 1))) {
                    ++end;
                }
                TreeNode curNode = new TreeNode(Integer.parseInt(s.substring(start, end + 1)));

                if (!stack.isEmpty()) {
                    TreeNode parentNode = stack.peek();
                    if (parentNode.left != null) {
                        parentNode.right = curNode;
                    }
                    else {
                        parentNode.left = curNode;
                    }
                }
                stack.push(curNode);
            }
        }
        return stack.isEmpty() ? null : stack.peek();
    }
}
```

## 3. Time & Space Complexity

**Recursion**: 时间复杂度O(n), 空间复杂度O(n)

**Iteration**: 时间复杂度O(n), 空间复杂度O(n)
