1
var recoverFromPreorder = function (traversal) {
2
  let n = traversal.length;
3

4
  // Every layer in dfs handles the depth+1 of '-' only.
5
  // ex:
6
  //   depth=0 -> find '-'  as splitter
7
  //   depth=1 -> find '--' as splitter
8
  //   depth=2 -> find '---' as splitter
9
  let dfs = (str, depth) => {
10
    if (str.indexOf("-") === -1) return new TreeNode(str);
11

12
    // 1. We split by the depth+1 number of '-'
13
    // Using regex to split is much easier. -> str.split(/(?<=\d)-(?=\d)/g)
14
    // where (?<=\d)  means positive lookbehind , ex: "1- ...", then we'll split '-' excluding 1.
15
    // Similarly , (?=\d) means positive lookahead , ex: "-5 ...",  then we'll split '-' excluding 5.
16

17
    let re = new RegExp(`(?<=\\d)${"-".repeat(depth + 1)}(?=\\d)`, "g");
18
    let [val, leftStr, rightStr] = str.split(re);
19
    // ex: 1-2--3--4-5--6--7 --> ['1','2--3--4','5--6--7']
20

21
    // 2. After splitting,  we'll get [val,leftStr,rightStr]
22
    // Then we could handle left / right node in the next dfs layer intuitively.
23
    let node = new TreeNode(val);
24
    if (leftStr) node.left = dfs(leftStr, depth + 1);
25
    if (rightStr) node.right = dfs(rightStr, depth + 1);
26

27
    return node;
28
  };
29

30
  return dfs(traversal, 0);
31
};