리프에서 시작하는 가장 작은 문자열

각 노드가 root ~ [0, 25] 문자를 나타내는 'a' 범위의 값을 갖는 이진 트리의 'z'가 제공됩니다.

이 트리의 리프에서 시작하여 루트에서 끝나는 사전순으로 가장 작은 문자열을 반환합니다.

참고로 문자열의 더 짧은 접두어는 사전순으로 더 작습니다.

예를 들어, "ab"는 "aba"보다 사전식으로 작습니다.

노드의 리프는 자식이 없는 노드입니다.

예 1:



입력: 루트 = [0,1,2,3,4,3,4]
출력: "dba"

예 2:



입력: 루트 = [25,1,3,1,3,0,2]
출력: "adz"

예 3:



입력: 루트 = [2,2,1,null,1,0,null,0]
출력: "abc"

제약:

트리의 노드 수가 [1, 8500] 범위에 있습니다.

0 <= Node.val <= 25

해결책:

# 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: Optional[TreeNode]) -> str:
        paths = [(root, [root.val] if root else [])]
        i = 0
        smallest = None
        while i < len(paths):
            curr, val = paths[i]
            if curr:
                if not curr.left and not curr.right:
                    n = len(val)
                    currval = "".join(["abcdefghijklmnopqrstuvwxyz"[val[i]] for i in range(n - 1, -1, -1)])
                    if smallest:
                        if currval < smallest:
                            smallest = currval
                    else:
                        smallest = currval
                if curr.left:
                    paths.append((curr.left, val + [curr.left.val]))
                if curr.right:
                    paths.append((curr.right, val + [curr.right.val]))
            i += 1
        return smallest