A binary tree is encoded by visiting each node before its left and right subtrees (preorder). Each node contributes its value preceded by one dash for every level of depth. The root has depth 0.
For example, a value at depth 2 is preceded by two dashes. Values are positive integers, so dashes only describe depth. Whenever a node has exactly one child, that child is its left child.
Given a valid encoding traversal, reconstruct the tree and return its root. The output examples show the tree in level order, using null for missing children and omitting trailing nulls.
Example 1:
Input: traversal = "8-3--6-12"
Output: [8,3,12,6]Explanation: The root is 8. The values 3 and 12 have one dash, so they are its left and right children. Value 6 has two dashes and follows 3, so it is the left child of 3.
Example 2:
Input: traversal = "20-7--11---4"
Output: [20,7,null,11,null,4]Explanation: Each successive value is one level deeper. The tree is a left-only chain: 20 has left child 7, then 11, then 4. Missing right children appear as null in level order.
Example 3:
Input: traversal = "9-2-5--4--6"
Output: [9,2,5,null,null,4,6]Explanation: The root is 9, with left child 2 and right child 5. Values 4 and 6 both have depth 2 and occur in the subtree of 5, making them its left and right children.
Constraints:
- The encoding represents a valid binary tree with
1to1000nodes. 1 <= Node.val <= 10^9- A node with exactly one child always has a left child.