Smallest String Starting From Leaf

Given therootof a binary tree, each node has a value from0to25representing the letters'a'to'z': a value of0represents'a', a value of1represents'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.)

1. 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.

分析

不能分治，因为要比较后缀而不是前缀，前缀大小不能决定结果：[[https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/244205/Divide-and-conquer-technique-doesn't-work-for-this-problem](https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/244205/Divide-and-conquer-technique-doesn't-work-for-this-problem](https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/244205/Divide-and-conquer-technique-doesn't-work-for-this-problem]%28https://leetcode.com/problems/smallest-string-starting-from-leaf/discuss/244205/Divide-and-conquer-technique-doesn't-work-for-this-problem)\)

The expected answer is "ababz", while by divide-and-conqure we would get "abz".
The problem here is

string X < string Y
doesn't guarantee

X + a < Y + a
where a is a character. e.g.:

"ab" < "abab", but "abz" > "ababz"

这里path就是后缀，没有左右子树了就可以更新res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:        
        if not root:
            return ""
        res = "~"
        def dfs(root,surfix):
            nonlocal res
            if not root:
                return 
            c = chr(root.val+97)+surfix
            if not root.left and not root.right and c < res:                
                res = c
            dfs(root.left, c)
            dfs(root.right,c)


        dfs(root,"")
        return res