BinarySearch 0844 Lexicographically Smallest Leaf to Root Path

Problem statement

https://binarysearch.com/problems/Lexicographically-Smallest-Leaf-to-Root-Path/

Solution

Equal to Leetcode 0988. Smallest String Starting From Leaf.

Complexity

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

Code

class Solution:
    def solve(self, root):
        def helps(node, path):
            if not node: return None
            if node.left == None and node.right == None:
                path += str(node.val)
                self.ans = min(self.ans, path[::-1])
                return
            helps(node.left,  path + str(node.val))
            helps(node.right, path + str(node.val))
            
        self.ans = "{"
        helps(root, "")
        return [int(i) for i in self.ans]