537. Tree in Brackets
A family-tree app needs a compact one-line text form of a binary tree root. The text of a leaf is just its integer value written in decimal (negative values keep their minus sign). The text of a node with at least one child is its value, followed by [, the text of its left child, the character |, the text of its right child, and ]. A missing child inside such a pair is written as a single underscore _. For example, a node 7 with only a left leaf 3 becomes 7[3|_]. Return the text of the whole tree, or the empty string when the tree is empty.
Example 1
- Input:
- root = [7,3,9]
- Output:
- "7[3|9]"
- Explanation:
Root 7 has two leaf children, so it is written as 7[3|9].
Example 2
- Input:
- root = [5,2,null,8]
- Output:
- "5[2[8|_]|_]"
- Explanation:
Node 5 has only a left child 2 (missing right gives _), and node 2 has only a left leaf 8.
Example 3
- Input:
- root = [4,null,6,null,1]
- Output:
- "4[_|6[_|1]]"
- Explanation:
The chain 4, 6, 1 goes through right children, so each missing left child is shown as an underscore.
Constraints
0 ≤ number of nodes ≤ 500
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)