Recover a Tree From Preorder Traversal

We walk a binary tree in preorder: first a node, then its whole left subtree, then its whole right subtree. For every node we write D dashes, where D is the node's depth, followed right away by the node's value. The root has depth 0, so it has no dashes; its children have depth 1, their children depth 2, and so on.

If a node has only one child, that child is its left child.

Given the string traversal written this way, rebuild the tree and return its root.

The tests print the tree you return level by level, from left to right, with null where a child is missing and the trailing nulls left out. For example, [1,2,null,3] is the tree with root 1, 2 as its left child and 3 as the left child of 2.

Example 1:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
       1
     /   \
    2     5
   / \   / \
  3   4 6   7

Explanation: "-2" and "-5" have one dash: they are the root's children, 2 first, so 2 is the left one. "--3" and "--4" come right after "-2", so they are the children of 2; "--6" and "--7" come after "-5", so they are the children of 5.

Example 2:

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]
        1
       / \
      2   5
     /   /
    3   6
   /   /
  4   7

Explanation: After "---4" (depth 3) comes "-5" (depth 1): the depth goes back up by two levels at once, so 5 is the second child of the root, its right child. Every node with a single child has it on the left.

Example 3:

Input: traversal = "5-12--7---40--9"
Output: [5,12,null,7,9,40]
      5
     /
    12
   /  \
  7    9
 /
40

Explanation: Values can have several digits: the dashes before a node end where its digits start. The root 5 has a single child, 12, so it is a left child.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Every node's value is between 1 and 109.
• traversal is a valid preorder walk of a tree, written as described above.