483. Tree to Text
A game server must save a binary tree of item levels as plain text so that it can be restored later. Write treeToText so that it converts the tree given by root into a string using a pre-order walk: visit a node, then its whole left subtree, then its whole right subtree. Every visited node is written as its value in decimal, and wherever a child is missing you write the single letter x instead. All tokens are joined by a single comma, with no spaces anywhere.
For example, a tree consisting of one node with value 4 becomes 4,x,x, because both of its children are missing. The empty tree is written as just x. Negative values keep their minus sign. The output must match this format exactly, because a different routine will parse it back.
Example 1
- Input:
- root = [6,2,9,null,4,7]
- Output:
- "6,2,x,4,x,x,9,7,x,x,x"
- Explanation:
Pre-order visits 6, 2, then 2's missing left child, 4 and so on, with x for each missing child.
Example 2
- Input:
- root = []
- Output:
- "x"
- Explanation:
An empty tree is written as a lone x.
Example 3
- Input:
- root = [-3,null,5]
- Output:
- "-3,x,5,x,x"
- Explanation:
The root -3 has no left child (x), then its right child 5 has two missing children.
Constraints
0 ≤ number of nodes ≤ 104
-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)