Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.
Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba".  A leaf of a node is a node that has no children.)


 





Example 1:

Input: [0,1,2,3,4,3,4]
Output: "dba"


Example 2:

Input: [25,1,3,1,3,0,2]
Output: "adz"


Example 3:

Input: [2,2,1,null,1,0,null,0]
Output: "abc"

 
Note:

The number of nodes in the given tree will be between 1 and 8500.
Each node in the tree will have a value between 0 and 25.

Source: leetcode | Difficulty: MEDIUM_HARD
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 smallestFromLeaf(self, root: TreeNode) -> str:
        

Solutions:
class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:

		def check(root):
			r = chr(root.val + 97)
			if root.left == None and root.right == None:
				return [r]
			r1 = []
			r2 = []
			if root.left != None:
				r1 = check(root.left)
			if root.right != None:
				r2 = check(root.right)
			rtv = []
			small = min(r1 + r2)
			for x in r1 + r2:
				if x.startswith(small):
					rtv.append(x + r)
			rtv.insert(0, small + r)
			return rtv
			pass
		rtv = check(root)
		return min(rtv)


class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:

		def dfs(node, path):
			nonlocal ans
			if node:
				path.append(letter_map[node.val])
				if not node.left and (not node.right):
					path_str = ''.join(reversed(path))
					if not ans:
						ans = path_str
					elif path_str < ans:
						ans = path_str
				else:
					pre_path = path.copy()
					if node.left:
						dfs(node.left, path)
					if node.right:
						dfs(node.right, pre_path)
		letter_map = []
		letter = 'a'
		for i in range(26):
			letter_map.append(letter)
			letter = chr(ord(letter) + 1)
		ans = None
		dfs(root, [])
		return ans


class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:
		if not root:
			return False
		stack = [(root, [])]
		res = 'zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz'
		while stack:
			(curr_node, path) = stack.pop()
			if not curr_node.left and (not curr_node.right):
				path.append(chr(97 + curr_node.val))
				path_rev = reversed(path)
				p = ''.join(path_rev)
				res = min(res, p)
			if curr_node.left:
				path1 = path.copy()
				path1.append(chr(97 + curr_node.val))
				stack.append((curr_node.left, path1))
			if curr_node.right:
				path1 = path.copy()
				path1.append(chr(97 + curr_node.val))
				stack.append((curr_node.right, path1))
		return res


class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:
		self.mapping = dict()
		for val in range(26):
			self.mapping[val] = chr(val + ord('a'))
		results = []
		self.dfs(root, [], results)
		results.sort()
		return results[0]

	def dfs(self, node, path, results):
		if not node.left and (not node.right):
			path.append(node.val)
			results.append(''.join([self.mapping[i] for i in path[::-1]]))
			path.pop()
			return
		path.append(node.val)
		if node.left:
			self.dfs(node.left, path, results)
		if node.right:
			self.dfs(node.right, path, results)
		path.pop()


class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:
		res = [26]

		def dfs(node, current):
			nonlocal res
			if not node.left and (not node.right):
				current.append(node.val)
				length = len(res)
				for (i, n) in enumerate(current[::-1]):
					if i < length and n < res[i]:
						res = current[::-1]
						return
					if i < length and n > res[i]:
						return
					if i >= length:
						return
				res = current[::-1]
				return
			current.append(node.val)
			if node.left:
				dfs(node.left, current[:])
			if node.right:
				dfs(node.right, current[:])
		dfs(root, [])
		li = 'abcdefghijklmnopqrstuvwxyz'
		ans = []
		for i in res:
			ans.append(li[i])
		return ''.join(ans)


class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:
		lists = self.recursiveSmallest(root)
		min_list = min(lists)
		return ''.join(min_list)

	def recursiveSmallest(self, node: TreeNode) -> List[str]:
		if node is None:
			return []
		if node.left is None and node.right is None:
			return [self.convert(node.val)]
		lists = []
		if node.left:
			smallest_left = self.recursiveSmallest(node.left)
			lists.extend(smallest_left)
		if node.right:
			smallest_right = self.recursiveSmallest(node.right)
			lists.extend(smallest_right)
		return [l + self.convert(node.val) for l in lists]

	def convert(self, value: int) -> str:
		a_value = ord('a')
		return chr(a_value + value)


class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:
		if root is None:
			return ''
		stack = [[root]]
		min_string = 'z' * 9999
		while stack:
			current = stack.pop()
			if current[-1].left is None and current[-1].right is None:
				min_string = min(min_string, ''.join((chr(65 + i.val).lower() for i in reversed(current))))
			if current[-1].left:
				stack.append(current + [current[-1].left])
			if current[-1].right:
				stack.append(current + [current[-1].right])
		return min_string


class Solution:

	def smallestFromLeaf(self, root: TreeNode) -> str:
		minStr = chr(ord('z') + 1)
		cList = []

		def dfs(root):
			nonlocal minStr
			nonlocal cList
			print(cList)
			cList.append(root.val)
			if not root.left and (not root.right):
				minStr = min(minStr, ''.join((string.ascii_lowercase[i] for i in cList[::-1])))
				cList.pop()
				return
			if root.left:
				dfs(root.left)
			if root.right:
				dfs(root.right)
			cList.pop()
		dfs(root)
		return minStr