##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1028.html

# 1028. Recover a Tree From Preorder Traversal (Hard)

We run a preorder depth first search 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: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]


Example 2:

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

Example 3:

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


Note:

• The number of nodes in the original tree is between 1 and 1000.
• Each node will have a value between 1 and 10^9.

## Solution 1. Stack

// OJ: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
// Time: O(S)
// Space: O(H) where H is depth of tree
class Solution {
private:
TreeNode *readNode(string &S, int &i) {
int n = 0;
for (; i < S.size() && isdigit(S[i]); ++i) n = 10 * n + S[i] - '0';
return new TreeNode(n);
}
int readDash(string &S, int &i) {
int cnt = 0;
for (; i < S.size() && S[i] == '-'; ++i, ++cnt);
return cnt;
}
public:
TreeNode* recoverFromPreorder(string S) {
int i = 0, N = S.size();
stack<TreeNode*> s;
s.push(root);
while (i < S.size()) {
while (dep < s.size()) s.pop();
auto p = s.top();
if (p->left) p->right = node;
else p->left = node;
s.push(node);
}
return root;
}
};


## Solution 2. DFS

// OJ: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
// Time: O(S)
// Space: O(H)
class Solution {
int curLevel;
TreeNode *curNode;
void dfs(istringstream &in, TreeNode *parent, int level) {
if (in.eof()) return;
curLevel = 0;
for (; in.peek() == '-'; in.get(), ++curLevel);
int n;
in >> n;
curNode = new TreeNode(n);
while (curNode && curLevel == level) {
if (!parent->left) parent->left = curNode;
else parent->right = curNode;
auto node = curNode;
curNode = NULL;
dfs(in, node, level + 1);
}
}
public:
TreeNode* recoverFromPreorder(string S) {
istringstream in(S);
int n;
in >> n;
auto root = new TreeNode(n);
dfs(in, root, 1);
return root;
}
};

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode recoverFromPreorder(String S) {
if (S == null || S.length() == 0)
return null;
StringBuffer sb = new StringBuffer(S);
for (int i = S.length() - 1; i > 0; i--) {
if (S.charAt(i) == '-' && S.charAt(i - 1) != '-')
sb.insert(i, ',');
}
String[] array = sb.toString().split(",");
int nodesCount = array.length;
int rootVal = Integer.parseInt(array[0]);
TreeNode root = new TreeNode(rootVal);
if (nodesCount == 1)
return root;
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack<Integer> levelStack = new Stack<Integer>();
nodeStack.push(root);
levelStack.push(0);
for (int i = 1; i < nodesCount; i++) {
String str = array[i];
int level = str.lastIndexOf('-') + 1;
int value = Integer.parseInt(str.substring(level));
TreeNode node = new TreeNode(value);
while (!levelStack.isEmpty() && levelStack.peek() >= level) {
nodeStack.pop();
levelStack.pop();
}
if (nodeStack.isEmpty())
return null;
TreeNode parent = nodeStack.peek();
if (parent.left == null)
parent.left = node;
else if (parent.right == null)
parent.right = node;
else
return null;
nodeStack.push(node);
levelStack.push(level);
}
return root;
}
}

• // OJ: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
// Time: O(S)
// Space: O(H) where H is depth of tree
class Solution {
private:
TreeNode *readNode(string &S, int &i) {
int n = 0;
for (; i < S.size() && isdigit(S[i]); ++i) n = 10 * n + S[i] - '0';
return new TreeNode(n);
}
int readDash(string &S, int &i) {
int cnt = 0;
for (; i < S.size() && S[i] == '-'; ++i, ++cnt);
return cnt;
}
public:
TreeNode* recoverFromPreorder(string S) {
int i = 0, N = S.size();
stack<TreeNode*> s;
s.push(root);
while (i < S.size()) {
while (dep < s.size()) s.pop();
auto p = s.top();
if (p->left) p->right = node;
else p->left = node;
s.push(node);
}
return root;
}
};

• # 1028. Recover a Tree From Preorder Traversal
# https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def recoverFromPreorder(self, A: str) -> Optional[TreeNode]:
stack = []
n = len(A)
index = 0

while index < n:
depth = 0

while index < n and A[index] == '-':
depth += 1
index += 1

val = 0
while index < n and A[index].isdigit():
val = val * 10 + int(A[index])
index += 1

while len(stack) > depth:
stack.pop()

node = TreeNode(val)

if stack:
if not stack[-1].left:
stack[-1].left = node
else:
stack[-1].right = node

stack.append(node)

while len(stack) > 1:
stack.pop()

return stack.pop()