Leetcode 988. Smallest String Starting From Leaf(python+cpp)

题目

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

错误解法：

原本想利用129的方法，先将所有的path以字符串的形式添加到一个列表中，然后在进行后续处理，但是这题跟129有点区别，因为这题节点值可能会大于10，所以不能这样

def smallestFromLeaf(self, root: TreeNode) -> str:def getnumber(root,number):if not root.left and not root.right:numberlist.append(number+str(root.val))returnif root.left:getnumber(root.left,number+str(root.val))if root.right:getnumber(root.right,number+str(root.val))if not root:return 0numberlist = []getnumber(root,'')_min = float('inf')for i in range(len(numberlist)):_sum = 0for char in numberlist[i]:_sum += int(char)if _min > _sum:index = i_min = _sumans = ''for char in reversed(numberlist[index]):ans += chr(int(char) + ord('a'))return numberlist

正确解法：

还是采用129类似的方法，但是在recursion的时候直接挑选最小的值。既当前节点为叶子节点时，比较形成的新线路与当前最小值进行比较。在python中用ord函数来得到字母的acsii值，用chr函数来将ascii值转回字母。而在C++中，字母可以直接加上数字变成新的字母

class Solution:def smallestFromLeaf(self, root: TreeNode) -> str:self.ans = '~'def helper(root,curr):if root:curr += chr(root.val+ord('a'))if not root.left and not root.right:self.ans = min(self.ans,curr[::-1])helper(root.left,curr)helper(root.right,curr)helper(root,'')return self.ans

时间复杂度：O(N *log N)，N为节点个数，每个节点比较的复杂度为O(logN)
空间复杂度：O(N)

C++解法

class Solution {
    
public:string ans = "~";void helper(TreeNode* root, string curr){
    if(root!=NULL){
    curr.push_back('a' + root->val);if(root->left==NULL && root->right==NULL){
    reverse(curr.begin(),curr.end());ans = min(ans,curr);}helper(root->left,curr);helper(root->right,curr);}}string smallestFromLeaf(TreeNode* root) {
    string s= "";helper(root,s);return ans;}
};