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 `S` of this traversal, recover the tree and return its `root`.

Example 1:

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

Example 2:

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

Example 3:

```Input: S = "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`

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
private int index;

public TreeNode recoverFromPreorder(String S) {
index = 0;
return recover(S, 0);
}

private TreeNode recover(String S, int depth) {
if (index == S.length()) {
return null;
}
int currIndex = index;
if (level != depth) {
index = currIndex;
return null;
}
TreeNode node = new TreeNode(val);
node.left = recover(S, depth + 1);
node.right = recover(S, depth + 1);
return node;
}

int level = 0;
while (index < S.length() && S.charAt(index) == '-') {
level++;
index++;
}
return level;
}

int val = 0;
while (index < S.length() && S.charAt(index) != '-') {
val = val * 10 + (S.charAt(index) - '0');
index++;
}
return val;
}
}```
```class Solution {
int index = 0;
public TreeNode recoverFromPreorder(String S) {
return helper(S, 0);
}

public TreeNode helper(String s, int depth) {
int numDash = 0;
while (index + numDash < s.length() && s.charAt(index + numDash) == '-') {
numDash++;
}
if (numDash != depth) return null;
int next = index + numDash;
while (next < s.length() && s.charAt(next) != '-') next++;
int val = Integer.parseInt(s.substring(index + numDash, next));
index = next;
TreeNode root = new TreeNode(val);
root.left = helper(s, depth + 1);
root.right = helper(s, depth + 1);
return root;
}
}```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/

// Sangam
class Solution {

String S = null;
int index = 0;
Integer nextNodeValue = null;
int nextHeight = 0;
public TreeNode recoverFromPreorder(String S) {
if (S.isEmpty()) return null;

this.S = S;
this.setNextNodeValue();
TreeNode root = new TreeNode(nextNodeValue);

recoverFromPreorder(nextHeight + 1, root);
return root;

}

public void recoverFromPreorder(int currentHeight, TreeNode root) {

this.setNextHeight();
this.setNextNodeValue();

if (currentHeight > this.nextHeight) return;
root.left = new TreeNode(nextNodeValue);
recoverFromPreorder(currentHeight + 1, root.left);

if (currentHeight > this.nextHeight) return;
root.right = new TreeNode(nextNodeValue);
recoverFromPreorder(currentHeight + 1, root.right);
}

public void setNextHeight() {
int height = 0;
while (index < S.length()) {
char ch = S.charAt(index);
if (ch == '-') {
height++;
index++;
continue;
}
break;
}
nextHeight = height;
}

public void setNextNodeValue() {
StringBuilder sb = new StringBuilder();
while (index < S.length() && S.charAt(index) != '-') {
sb.append(S.charAt(index));
index++;
}
if (sb.length() == 0) return;
nextNodeValue = Integer.parseInt(sb.toString());
}
}```
Previous Post

Next article