## Algorithm

Problem Name: 1028. Recover a Tree From Preorder Traversal

We run a preorder depth-first search (DFS) on the `root` of a binary tree.

At each node in this traversal, we output `D` dashes (where `D` is the depth of this node), then we output the value of this node.  If the depth of a node is `D`, the depth of its immediate child is `D + 1`.  The depth of the `root` node is `0`.

If a node has only one child, that child is guaranteed to be the left child.

Given the output `traversal` of this traversal, recover the tree and return its `root`.

Example 1:

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

Example 2:

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

Example 3:

```Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]
```

Constraints:

• The number of nodes in the original tree is in the range `[1, 1000]`.
• `1 <= Node.val <= 109`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public TreeNode recoverFromPreorder(String S) {
Map map = new HashMap<>();
int idx = 0;
int n = S.length();

while (idx < n) {
int level = 0;
StringBuilder sb = new StringBuilder();

while (idx < n && S.charAt(idx) == '-') {
level++;
idx++;
}

while (idx < n && Character.isDigit(S.charAt(idx))) {
sb.append(S.charAt(idx++));
}

TreeNode currNode = new TreeNode(Integer.parseInt(sb.toString()));
map.put(level, currNode);
if (level > 0) {
TreeNode parent = map.get(level - 1);
if (parent.left == null) {
parent.left = currNode;
}
else {
parent.right = currNode;
}
}
}

return map.get(0);
}
}
``````
Copy The Code &

Input

cmd
traversal = "1-2--3--4-5--6--7"

Output

cmd
[1,2,5,3,4,6,7]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const recoverFromPreorder = function(S) {
const arr = []
let tmp = S[0]
for(let i = 1; i < S.length; i++) {
if(S[i] === '-') {
if(S[i-1] === '-') {
tmp += '-'
} else {
arr.push(tmp)
tmp = '-'
}
} else {
if(S[i-1] === '-') {
arr.push(tmp)
tmp = S[i]
} else {
tmp += S[i]
}
}
}
arr.push(tmp)
const resArr = []
helper(resArr, arr, 0)
return resArr[0]
};

function helper(nodeArr, strArr, idx) {
if(idx >= strArr.length) return
if(idx > 0) {

if(strArr[idx].startsWith('-')) {
helper(nodeArr, strArr, idx + 1)
} else {
nodeArr[idx] = new TreeNode(+strArr[idx])
let d = strArr[idx - 1].length

let tIdx

for(let i = idx - 1; ; i = i - 2) {
if(i>= 1) {
if(strArr[i].length < d) {
tIdx = i+1
break
}
} else {

tIdx = 0
break
}
}

if(nodeArr[tIdx].left) {
nodeArr[tIdx].right = nodeArr[idx]
} else {
nodeArr[tIdx].left = nodeArr[idx]
}
helper(nodeArr, strArr, idx + 1)
}

} else {
nodeArr[idx] = new TreeNode(+strArr[idx])
helper(nodeArr, strArr, idx + 1)
}

}
``````
Copy The Code &

Input

cmd
traversal = "1-2--3--4-5--6--7"

Output

cmd
[1,2,5,3,4,6,7]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def recoverFromPreorder(self, S: str) -> TreeNode:
def dfs(parent, s, lev):
print(parent.val, s, lev)
if not s: return
i = lev
l = 0
while i < len(s) and s[i].isdigit():
l = l * 10 + int(s[i])
i += 1
parent.left = TreeNode(l)
j = lev
f = '-' * lev
for ind in range(i, len(s)):
if s[ind:].startswith(f) and not s[ind:].startswith(f + '-') and s[ind -1] != '-':
rr = ind
j = ind + lev
r = 0
while j < len(s) and s[j].isdigit():
r = r * 10 + int(s[j])
j += 1
parent.right = TreeNode(r)
dfs(parent.left, s[i:rr], lev + 1)
dfs(parent.right, s[j:], lev + 1)
return
dfs(parent.left, s[i:], lev + 1)
i = num = 0
while i < len(S) and S[i].isdigit():
num = num * 10 + int(S[i])
i += 1
root = TreeNode(num)
dfs(root, S[i:], 1)
return root
``````
Copy The Code &

Input

cmd
traversal = "1-2--3---4-5--6---7"

Output

cmd
[1,2,5,3,null,6,null,4,null,7]