Medium

Quiz

#606 Construct String from Binary Tree

APPROACH

Given the root of a binary tree, build a preorder-traversal string using these rules: represent each node by its integer value; wrap each child's representation in parentheses placed after the parent's value; omit empty parentheses unless a node has a right child but no left child — in that case, include () as a placeholder for the missing left child to preserve structural uniqueness.

Example 1:

Input: root = [1,2,3,4]

Output: "1(2(4))(3)"

Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

Example 2:

Input: root = [1,2,3,null,4]

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, except the () after 2 is necessary to indicate the absence of a left child for 2 and the presence of a right child.

1 of 4

1:00

What is the optimal approach for this problem?