Sponsored
Sponsored
In this approach, we utilize depth-first search to explore each path from the leaf to the root. We maintain the current path in a string, which is reversed each time we reach a leaf node. We then compare it to the currently known smallest string, updating the smallest string if the new path is smaller.
Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
1class Solution:
2 def smallestFromLeaf(self, root: TreeNode) -> str:
3 def dfs(node, path):
4 if not node:
5 return
6 # Prepend character corresponding to the current node's value to the path
7 path = chr(node.val + ord('a')) + path
8 # If leaf node
9 if not node.left and not node.right:
10 nonlocal smallest
11 if path < smallest:
12 smallest = path
13 # Recurse to children
14 dfs(node.left, path)
15 dfs(node.right, path)
16
17 smallest = "~" # Start with a string larger than any possible result
18 dfs(root, "")
19 return smallest
20This solution uses a DFS approach to explore all paths from leaf nodes to the root. We build the path string by prepending the current node's character (converted from the node's value) to the path. Upon reaching a leaf node, we compare the constructed path to the smallest recorded path. If it's smaller, we update our smallest value. Finally, we use recursion to explore both left and right children of each node.