You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.
Return 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: root = [0,1,2,3,4,3,4]
Output: "dba"
Example 2:
Input: root = [25,1,3,1,3,0,2]
Output: "adz"
Example 3:
Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"
Constraints:
- The number of nodes in the tree is in the range
[1, 8500]. -
0 <= Node.val <= 25
SOLUTION:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
paths = [(root, [root.val] if root else [])]
i = 0
smallest = None
while i < len(paths):
curr, val = paths[i]
if curr:
if not curr.left and not curr.right:
n = len(val)
currval = "".join(["abcdefghijklmnopqrstuvwxyz"[val[i]] for i in range(n - 1, -1, -1)])
if smallest:
if currval < smallest:
smallest = currval
else:
smallest = currval
if curr.left:
paths.append((curr.left, val + [curr.left.val]))
if curr.right:
paths.append((curr.right, val + [curr.right.val]))
i += 1
return smallest
Top comments (0)