Construct Binary Tree from String

Given a string representation of a binary tree where each node value is followed by child subtrees in parentheses, construct the tree and return it as a level-order array. Pattern focus: Construct Tree from Traversals. Parse the string recursively and rebuild the tree structure.

Input Format

treeString = string representation of the binary tree

Output Format

level-order array representation of the reconstructed tree

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

treeString = "4(2(3)(1))(6(5))"

Output:

[4,2,6,3,1,5]

Explanation:

The string encodes a tree with root 4, left subtree 2, and right subtree 6.

Example 2:

Input:

treeString = "1(2)(3)"

Output:

[1,2,3]

Explanation:

A simple root with two children.

Loading...
Construct Binary Tree from String - Binary Tree