Formatted question description: https://leetcode.ca/all/536.html

# 536. Construct Binary Tree from String

Medium

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

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 "()".

## Solution

First consider the cases when the tree is empty or contains only one node. Simply return null or the single node in such cases.

Loop over the string and split the terms '(' and ')' with other terms. Use the idea of preorder traversal, where two stacks are used to store nodes and strings. If a '(' is met, then push the '(' into the string stack. If a ')' is met, then pop both stacks until the string stack’s top element is '(', and pop '(' from the string stack. If a number is met, create a new node with the number as the value, and find its parent at the top of the node stack. Set the current node to be its parent’s left node or right node depending on whether the parent’s left node is null.

Finally, return the root of the tree.