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.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

String algorithms

Starter code: # 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, S: str) -> TreeNode:
        

Solutions:
import re

class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		itera = re.finditer('(-*)(\\\\d+)', S)
		root = TreeNode(int(next(itera).group(2)))
		tofill = [root]
		for m in itera:
			k = len(m.group(1))
			if k == len(tofill):
				node = TreeNode(int(m.group(2)))
				tofill[-1].left = node
				tofill.append(node)
			else:
				node = TreeNode(int(m.group(2)))
				tofill[k - 1].right = node
				tofill[k:] = [node]
		return root


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		ptr = 0

		def traverse(level: int) -> TreeNode:
			nonlocal ptr
			nextLevel = 0
			while ptr < len(S) and S[ptr] == '-':
				nextLevel += 1
				ptr += 1
			if level == nextLevel:
				val = ''
				while ptr < len(S) and S[ptr] != '-':
					val += S[ptr]
					ptr += 1
				node = TreeNode(int(val))
				node.left = traverse(level + 1)
				node.right = traverse(level + 1)
				return node
			else:
				ptr -= nextLevel
				return None
		return traverse(0)


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:

		def dfs(s, idx, depth):
			if idx == len(s):
				return (None, len(s))
			cnt = 0
			while s[cnt + idx] == '-':
				cnt += 1
			if cnt != depth:
				return (None, idx)
			idx += cnt
			i = 0
			while idx + i < len(s) and s[idx + i].isdigit():
				i += 1
			root = TreeNode(int(s[idx:idx + i]))
			idx += i
			(root.left, li) = dfs(s, idx, depth + 1)
			(root.right, ri) = dfs(s, li, depth + 1)
			return (root, ri)
		return dfs(S, 0, 0)[0]


class Solution:

	def recoverFromPreorder(self, s: str) -> TreeNode:
		self.index = 0

		def dfs(depth):
			if self.index == len(s):
				return
			for i in range(depth):
				if s[self.index + i] != '-':
					return
			self.index += depth
			curr = 0
			while self.index < len(s) and s[self.index].isdigit():
				curr = curr * 10 + int(s[self.index])
				self.index += 1
			node = TreeNode(curr)
			node.left = dfs(depth + 1)
			node.right = dfs(depth + 1)
			return node
		return dfs(0)


def getNext(s, i):
	c = 0
	while i < len(s) and s[i] == '-':
		i += 1
		c += 1
	num = []
	if i == len(s):
		return (-1, -1, -1)
	while i < len(s) and s[i] != '-':
		num.append(s[i])
		i += 1
	return (c, int(''.join(num)), i)
(c, num, i) = (0, 0, 0)

def solve(s, level):
	nonlocal c, num, i
	(c, num, j) = getNext(s, i)
	if c == -1 or c < level:
		return None
	node = TreeNode(num)
	i = j
	node.left = solve(s, level + 1)
	node.right = solve(s, level + 1)
	return node

class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		nonlocal c, num, i
		(c, num, i) = (0, 0, 0)
		return solve(S, 0)


class Solution:

	def recoverFromPreorder(self, S):
		(stack, i) = ([], 0)
		while i < len(S):
			(level, val) = (0, '')
			while i < len(S) and S[i] == '-':
				(level, i) = (level + 1, i + 1)
			while i < len(S) and S[i] != '-':
				(val, i) = (val + S[i], i + 1)
			while len(stack) > level:
				stack.pop()
			node = TreeNode(val)
			if stack and stack[-1].left is None:
				stack[-1].left = node
			elif stack:
				stack[-1].right = node
			stack.append(node)
		return stack[0]


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		if not S:
			return None
		self.idx = 0
		return self.recoverTree(S, 0)

	def recoverTree(self, s, depth):
		d = self.getDepth(s)
		if d != depth:
			self.idx -= d
			return
		root = TreeNode(self.getVal(s))
		root.left = self.recoverTree(s, depth + 1)
		root.right = self.recoverTree(s, depth + 1)
		return root

	def getDepth(self, s):
		d = 0
		while self.idx < len(s) and s[self.idx] == '-':
			d += 1
			self.idx += 1
		return d

	def getVal(self, s):
		num = 0
		while self.idx < len(s) and s[self.idx].isdigit():
			num = num * 10 + int(s[self.idx])
			self.idx += 1
		return num


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:

		def _recoverFromPreorder(s):
			if not s:
				return
			root = TreeNode(s.pop())
			depth = 0
			while s:
				if s[-1] == '-':
					s.pop()
					depth += 1
				else:
					break
			var = 0
			index = -1
			for i in range(len(s) - 1, -1, -1):
				if s[i] != '-':
					if var == depth:
						index = i
						break
					var = 0
				else:
					var += 1
			if index == -1:
				root.left = _recoverFromPreorder(s)
			else:
				root.right = _recoverFromPreorder(s[:index + 1])
				root.left = _recoverFromPreorder(s[index + depth + 1:])
			return root
		arr = list(S)
		arr_1 = []
		x = ''
		while arr:
			s = arr.pop()
			if s == '-':
				if x:
					arr_1.append(x)
				arr_1.append(s)
				x = ''
			else:
				x = s + x
		if x:
			arr_1.append(x)
		return _recoverFromPreorder(arr_1)


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		dashes = 0
		stk = []
		i = 0
		while i < len(S):
			s = S[i]
			if s.isnumeric():
				c = s
				while i + 1 < len(S) and S[i + 1].isnumeric():
					c += S[i + 1]
					i += 1
				while stk and dashes != stk[-1][1] + 1:
					stk.pop()
				node = TreeNode(int(c))
				if stk and stk[-1][0].left:
					stk[-1][0].right = node
				elif stk:
					stk[-1][0].left = node
				stk.append((node, dashes))
				dashes = 0
			else:
				dashes += 1
			i += 1
		return stk[0][0]


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		return self.helper(S, 0)

	def helper(self, S, level):
		if not S:
			return None
		val = self.get(S)
		node = TreeNode(val)
		(idx1, idx2) = self.find(S, level)
		if idx1:
			node.left = self.helper(S[idx1:idx2], level + 1)
		if idx2:
			node.right = self.helper(S[idx2:], level + 1)
		return node

	def find(self, S, level):
		idx1 = idx2 = None
		count = 0
		for (i, ch) in enumerate(S):
			if ch != '-':
				if count == level + 1:
					if not idx1:
						idx1 = i
					else:
						idx2 = i
						return (idx1, idx2)
				count = 0
			else:
				count += 1
		return (idx1, idx2)

	def get(self, S):
		val = ''
		for ch in S:
			if ch == '-':
				break
			val += ch
		return val


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		if S == '':
			return
		root = TreeNode(S.split('-')[0])
		stack = [(root, 0)]
		nodes = []
		i = len(root.val)
		depth = 0
		val = []
		started = False
		while i < len(S):
			if S[i] == '-':
				if started:
					nodes.append((TreeNode(''.join(val)), depth))
					depth = 0
					val = []
					started = False
				depth += 1
			else:
				started = True
				val.append(S[i])
			i += 1
		nodes.append((TreeNode(''.join(val)), depth))
		print(nodes)
		for node in nodes:
			while len(stack) > 0 and node[1] <= stack[-1][1]:
				stack.pop()
			if len(stack) > 0:
				parent = stack[-1][0]
				if parent.left is None:
					parent.left = node[0]
				else:
					parent.right = node[0]
			stack.append(node)
		return root


class Solution:

	def transform(self, string):
		s = string.split('-')
		i = 1
		res = [(s[0], 0)]
		while i < len(s):
			l = 1
			if s[i] == '':
				while s[i] == '':
					i += 1
					l += 1
			res.append((int(s[i]), l))
			i += 1
		return res

	def recoverFromPreorder(self, S: str) -> TreeNode:
		L = {}
		trans = self.transform(S)
		L[0] = TreeNode(trans[0][0])
		for (val, lvl) in trans[1:]:
			L[lvl] = TreeNode(val)
			if L[lvl - 1].left:
				L[lvl - 1].right = L[lvl]
			else:
				L[lvl - 1].left = L[lvl]
		return L[0]


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		if not S:
			return None
		if '-' not in S:
			return TreeNode(int(S))
		(dashes, ind, n) = (0, 1, len(S))
		while ind < n and S[ind] >= '0' and (S[ind] <= '9'):
			ind += 1
		root = TreeNode(S[:ind])
		while ind < n and S[ind] == '-':
			ind += 1
			dashes += 1
		left_ind = ind
		dashes_right = 0
		while ind < n:
			dashes_right = 0
			while ind < n and S[ind] >= '0' and (S[ind] <= '9'):
				ind += 1
			while ind < n and S[ind] == '-':
				dashes_right += 1
				ind += 1
			if dashes_right == dashes:
				break
		if dashes_right == dashes:
			root.left = self.recoverFromPreorder(S[left_ind:ind - dashes_right])
			root.right = self.recoverFromPreorder(S[ind:])
		else:
			root.left = self.recoverFromPreorder(S[left_ind:])
		return root


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		self.i = 0
		return self.construct_tree(S, 0)

	def construct_tree(self, S, level):
		if self.i == len(S):
			return None
		zero = ord('0')
		j = self.i
		node_lvl = 0
		while j < len(S) and S[j] == '-':
			node_lvl += 1
			j += 1
		val = 0
		while j < len(S) and S[j].isdigit():
			val = val * 10 + (ord(S[j]) - zero)
			j += 1
		if level != node_lvl:
			return None
		self.i = j
		return TreeNode(val, self.construct_tree(S, level + 1), self.construct_tree(S, level + 1))


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		if not S:
			return
		ins = list(S)
		root = TreeNode(-1)
		current = None
		while ins:
			while ins and ins[0] == '-':
				if current.right:
					current = current.right
				elif current.left:
					current = current.left
				ch = ins.pop(0)
			node_val = ''
			while ins and ins[0] != '-':
				ch = ins.pop(0)
				node_val += ch
			if not root.left:
				root.left = TreeNode(node_val)
			elif not current.left:
				current.left = TreeNode(node_val)
			else:
				current.right = TreeNode(node_val)
			current = root
		return root.left


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:

		def helper(current_depth, s):
			split_point1 = -1
			split_point2 = -1
			next_depth = current_depth + 1
			count = 0
			whole_count = 0
			for (index, c) in enumerate(s):
				if c == '-':
					whole_count += 1
					count += 1
				else:
					if count == next_depth:
						if split_point1 == -1:
							split_point1 = index
						else:
							split_point2 = index
					count = 0
			if whole_count == 0:
				return TreeNode(int(s))
			else:
				root = TreeNode(int(s[:split_point1 - next_depth]))
				if split_point2 != -1:
					root.left = helper(next_depth, s[split_point1:split_point2 - next_depth])
					root.right = helper(next_depth, s[split_point2:])
				else:
					root.left = helper(next_depth, s[split_point1:])
					root.right = None
			return root
		return helper(0, S)


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		idx = 0
		while idx < len(S) and S[idx] != '-':
			idx += 1
		root = TreeNode(int(S[:idx]))
		root_l = idx
		if len(S) == idx:
			return root
		d = 0
		while S[idx] == '-':
			d += 1
			idx += 1
		cnt = 0
		while idx < len(S):
			if S[idx] != '-':
				if cnt == d:
					root.left = self.recoverFromPreorder(S[root_l + d:idx - d])
					root.right = self.recoverFromPreorder(S[idx:])
					break
				cnt = 0
			else:
				cnt += 1
			idx += 1
			if idx == len(S):
				root.left = self.recoverFromPreorder(S[root_l + d:])
		return root


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		try:
			self.values = [int(i) for i in S.split('-') if len(i) > 0]
			self.S = S[S.index('-'):]
			root = TreeNode(self.values.pop(0))
		except:
			return TreeNode(int(S))

		def create_tree(root, depth):
			if len(self.S) == 0:
				return
			elif '-' * depth == self.S[:depth]:
				if root.left == None:
					num = self.values.pop(0)
					digits = len(str(num))
					tmp = TreeNode(num)
					self.S = self.S[depth + digits:]
					create_tree(tmp, depth + 1)
					root.left = tmp
				if root.right == None and '-' * depth == self.S[:depth]:
					num = self.values.pop(0)
					digits = len(str(num))
					tmp = TreeNode(num)
					self.S = self.S[depth + digits:]
					create_tree(tmp, depth + 1)
					root.right = tmp
				return root
			elif '-' * depth != self.S[:depth]:
				return
		return create_tree(root, 1)


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		root_num = ''
		start = 0
		while S[start].isdigit():
			root_num += S[start]
			start += 1
			if start == len(S):
				break
		div = [(0, int(root_num))]
		depth_counter = 0
		while start < len(S):
			if S[start] == '-':
				depth_counter += 1
				start += 1
			else:
				num = ''
				while S[start].isdigit():
					num += S[start]
					start += 1
					if start == len(S):
						break
				div.append((depth_counter, int(num)))
				depth_counter = 0
		res = TreeNode(int(root_num))
		track = res
		dicts = {0: res}
		for i in range(1, len(div)):
			(depth, val) = (div[i][0], div[i][1])
			roots = dicts[depth - 1]
			if not roots.left:
				roots.left = TreeNode(val)
				dicts[depth] = roots.left
			else:
				roots.right = TreeNode(val)
				dicts[depth] = roots.right
		return res


class Solution:

	def recoverFromPreorder(self, S: str) -> TreeNode:
		if not S:
			return None
		i = 0
		d = 0
		s = []
		v = 0
		while i < len(S) and S[i].isdigit():
			v = v * 10 + int(S[i])
			i += 1
		root = TreeNode(v)
		s.append((root, d))
		while i < len(S):
			if S[i].isdigit():
				v = 0
				while i < len(S) and S[i].isdigit():
					v = v * 10 + int(S[i])
					i += 1
				nnode = TreeNode(v)
				if not s:
					s.append((nnode, d))
				else:
					node = s.pop()
					while s and node[1] != d - 1:
						node = s.pop()
					if not node[0].left:
						node[0].left = nnode
						s.append(node)
					else:
						node[0].right = nnode
					s.append((nnode, d))
			else:
				d = 0
				while i < len(S) and S[i] == '-':
					d += 1
					i += 1
		return root