难度: Medium
原题连接
内容描述
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 1000.
Each node in the tree will have a value between 0 and 25.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******
递归
class Solution:
def smallestFromLeaf(self, root: 'TreeNode') -> 'str':
def trans(val):
return chr(ord('a') + val)
def helper(node):
if not node:
return ''
elif not node.left and not node.right:
return trans(node.val)
elif not node.left and node.right: # 因为必须要从 leaf node开始，所以必须选择 helper(node.right)
return helper(node.right) + trans(node.val)
elif node.left and not node.right: # 因为必须要从 leaf node开始，所以必须选择 helper(node.left)
return helper(node.left) + trans(node.val)
else:
return min(helper(node.left) + trans(node.val), helper(node.right) + trans(node.val))
return helper(root)