485. Text to Tree
A game server stores a binary tree of item levels as text and now has to rebuild the tree. The string data was produced by a pre-order walk (a node, then its whole left subtree, then its whole right subtree): each existing node is written as its integer value, each missing child is written as the single letter x, and all tokens are separated by single commas without spaces. For instance, 4,x,x is a lone node with value 4, and the empty tree is simply x.
Write textToTree so that it rebuilds the tree and returns its root, or returns an empty tree when data describes none. The string is always well formed, and exactly one tree matches it. Values may be negative.
Example 1
- Input:
- data = "4,1,x,3,x,x,8,x,x"
- Output:
- [4,1,8,null,3]
- Explanation:
Node 4 has left child 1 (whose right child is 3) and right child 8.
Example 2
- Input:
- data = "x"
- Output:
- []
- Explanation:
A lone x describes the empty tree.
Example 3
- Input:
- data = "5,x,7,6,x,x,x"
- Output:
- [5,null,7,6]
- Explanation:
Root 5 has no left child; its right child 7 has left child 6.
Constraints
The tree described by data has 0 ≤ number of nodes ≤ 104
-1000 ≤ Node.val ≤ 1000
data is a valid text in the format described above.
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)