404. Construct Binary Tree from String
You receive a string s that describes a binary tree in a compact recursive format: a node is written as its integer value (possibly negative), followed by zero, one, or two groups wrapped in parentheses. The first group contains the node's left subtree and the second its right subtree, each written in the same format.
A node that has only a right child marks the missing left child with an empty group (); parentheses for absent children at the end are simply omitted. So 4(2(3)(1))(6(5)) is a root 4 whose left subtree is 2(3)(1) and whose right subtree is 6(5), while 1()(2) is a root 1 with no left child and a right child 2.
Parse s, build the tree, and return its root.
The judge prints your tree in level order: node values separated by single spaces, with null standing in for a missing child of a printed node, and trailing null tokens removed.
Example 1:
Input: tree_from_string("4(2(3)(1))(6(5))")
Output: the tree [4, 2, 6, 3, 1, 5]
Explanation: Root 4; its left group 2(3)(1) is a node 2 with children 3 and 1; its right group 6(5) is a node 6 whose only child, 5, is a left child (a single group is always the left subtree).
Example 2:
Input: tree_from_string("1()(2)")
Output: the tree [1, null, 2]
Explanation: The empty group () says node 1 has no left child, so the 2 in the second group hangs on the right.
Constraints:
- 1 ≤ s.length ≤ 3 * 10⁴
- -10⁴ ≤ node value ≤ 10⁴
- s contains only digits, '-', '(' and ')'
- s describes a valid binary tree
Hints:
The format is self-similar: a value, then optionally (left subtree), then optionally (right subtree) — each subtree written the same way. A grammar that refers to itself begs for a recursive-descent parser: one function that parses a node and calls itself for the children.
Keep a single cursor shared by every call. Parse the (possibly negative) number under the cursor; then, each time the cursor sits on '(', step past it, recurse to build the child, and consume the matching ')'. If the cursor sees ')' immediately after stepping in, the group is empty — return no node.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "4(2(3)(1))(6(5))"
Expected output: [4, 2, 6, 3, 1, 5]