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.

Difficulty: interview

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:
# 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:
        nonlocal ls
        ls=[]
        di={0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g', 7: 'h', 8: 'i', 9: 'j', 10: 'k', 11: 'l', 12: 'm', 13: 'n', 14: 'o', 15: 'p', 16: 'q', 17: 'r', 18: 's', 19: 't', 20: 'u', 21: 'v', 22: 'w', 23: 'x', 24: 'y', 25: 'z'}
        def helper(root,s):
            if(root==None):
                return None
            nonlocal ls
            if(root.left==None and root.right==None):
                ls.append(di[root.val]+s)
            
            helper(root.left,di[root.val]+s)
            helper(root.right,di[root.val]+s)
            
        helper(root,\"\")
        print(ls)
        # tem=sorted(ls)[0]
        tem=sorted(ls)
        return tem[0]
        # ans=\"\"
        # for i in tem:
        #     ans+=str(di[int(i)])
        # return ans
            

# 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:
        \"\"\"
        8:00 AM
        
        \"\"\"
        if root == None:
            return \"\"
        result  = None
        
        charMappings = { i: chr(i+ord(\"a\")) for i in range(0, 26)}
        
        def helper(node, path):
            nonlocal result
            if node == None:
                return
            
            if node.left == None and node.right == None:
                char = charMappings.get(node.val)
                string = \"\".join(  ((path+[char])[::-1]) )
                if result == None or string < result:
                    result = string
                
                return
            char = charMappings.get(node.val)
            helper(node.left, path+[char])
            helper(node.right, path+[char])
            
        helper(root, [])
        return result
                

# 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:
        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
        
        #   输入非空：The number of nodes in the given tree will be between 1 and 8500.
        rtv = check(root)
        return min(rtv)

# 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:
    # 10:35
    def helper(self, root, path):
        if root == None:
            return path
        else:
            my_path = chr(ord('a') + root.val) + path
            left = self.helper(root.left, my_path)
            right = self.helper(root.right, my_path) 
            if root.left == None:
                ans = right
            elif root.right == None:
                ans = left
            else:
                ans = min(left, right)
            return ans
        
    def smallestFromLeaf(self, root: TreeNode) -> str:
        path = \"\"
        return self.helper(root, path)

# 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:
        def dfs(node, path):
            nonlocal ans
            if node:
                path.append(letter_map[node.val])
                if not node.left and not node.right:  # leaf
                    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


# 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:
        # DFS from root to leaf
        
        
        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


# 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:
        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:
        #     results.append(''.join([self.mapping[i] for i in path[::-1]]))
        #     return
        
        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()


# 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
import string
class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:   
        def pathToLeaf(root, letters):
            nonlocal smallest
            if root:
                letters+=chr(root.val + ord('a'))
                if root.right == None and root.left == None:
                    reversed_letters = letters[::-1]
                    if smallest > reversed_letters:
                        smallest =  reversed_letters
                else:
                    pathToLeaf(root.left, letters)
                    pathToLeaf(root.right,  letters)
        
        smallest = \"~\"
        pathToLeaf(root, \"\")
        return smallest
            

# 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
import string
class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:   
        def pathToLeaf(root, letters, alphabet):
            nonlocal smallest
            if root:
               # count_path+=root.val
                letters+=alphabet[root.val]
                if root.right == None and root.left == None:
                    reversed_letters = letters[::-1]
                    if smallest > reversed_letters:
                        smallest =  reversed_letters
                else:
                    pathToLeaf(root.left, letters, alphabet)
                    pathToLeaf(root.right,  letters, alphabet)
        
        alphabet = dict( (i, letter) for i, letter in enumerate(string.ascii_lowercase))
        smallest = \"~\"
        pathToLeaf(root, \"\", alphabet)
        return smallest
            

# 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:
        
        self.result = \"z\"*10000
        stack = []
        
        def traverse(node: TreeNode) -> str :
            if node:
                stack.append(chr(node.val + 97))
                if not node.left and not node.right:
                    self.result = min(self.result, \"\".join(reversed(stack)))                    
                traverse(node.left)
                traverse(node.right)
                stack.pop()                            
        
        traverse(root)
        return self.result
                    
            
        

# 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


def helper(root: TreeNode) -> str:
    if root is None:
        return [\"\"]
    
    s = chr(ord('a') + root.val)
    
    if root.left is None and root.right is None:
        return [s]
    elif root.left is None:
        return [_ + s for _ in helper(root.right)]
    elif root.right is None:
        return [_ + s for _ in helper(root.left)]
    else:
        left = [_ + s for _ in helper(root.left)]
        right = [_ + s for _ in helper(root.right)]

        return left + right


class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:
        return min(helper(root))
        

# 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:
        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)

# 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:
        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)

# 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:
        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


# 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:
    #string.ascii_lowercase
    def smallestFromLeaf(self, root: TreeNode) -> str:
        minStr = chr(ord('z')+1)
        #print(minStr)
        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