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.)
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.
分析
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
