Leetcode 0988. Smallest String Starting From Leaf

Problem statement

https://leetcode.com/problems/smallest-string-starting-from-leaf/

Solution

At the moment, I think that the only solution which will work it bruteforce: we need to iterate until leafs, create string and then choose the smallest inversed string. Other solutions, like we use postorder dfs will not work here.

Complexity

It is O(n * h) for time and O(h^2) for space.

Code

class Solution:
    def smallestFromLeaf(self, root):
        def helps(node, path):
            if not node: return None
            if node.left == None and node.right == None:
                path += chr(node.val + 97)
                self.ans = min(self.ans, path[::-1])
                return
            helps(node.left,  path + chr(97 + node.val))
            helps(node.right, path + chr(97 + node.val))
            
        self.ans = "{"
        helps(root, "")
        return (self.ans)