426. Construct String from Binary Tree
You are given the root of a binary tree (a TreeNode with val, left, and right; the tree has at least one node). Encode the tree into a single string using a preorder format: write the node's value, then its left subtree wrapped in parentheses, then its right subtree wrapped in parentheses.
To keep the string as short as possible while still decoding back to the same tree, drop every parenthesis pair that carries no information:
- a leaf contributes just its value — no parentheses at all;
- a missing right child is written as nothing;
- a missing left child whose right sibling exists must keep its empty
()— without it, the right subtree would be misread as the left one.
Return the resulting string.
Example 1:
Input: root = [1, 2, 3, 4]
Output: "1(2(4))(3)"
Explanation: Node 2 has only a left child 4, so 4 is wrapped once and no empty pair is needed; 2's subtree becomes 2(4). The right child 3 is a leaf, wrapped as (3).
Example 2:
Input: root = [1, 2, 3, null, 4]
Output: "1(2()(4))(3)"
Explanation: Node 2 has a right child 4 but no left child, so the empty () must stay — 2(4) alone would decode with 4 as the LEFT child, a different tree.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -1000 ≤ Node.val ≤ 1000
Hints:
Think per node: when do you print parentheses after the value? The left pair appears whenever the node has ANY child; the right pair appears only when the right child exists.
Recurse in preorder and let each call return (or append) its subtree's encoding. The case analysis is just: leaf → val; left only → val(L); right only → val()(R); both → val(L)(R).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4]
Expected output: "1(2(4))(3)"