Smallest String Starting From Leaf

Problem Id: 988 Difficulty: Medium Tag: Tree Tag: Depth-first Search


Intuition

This problem could be solved using brute force directly, by one single DFS.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import string


class Solution:
    def smallestFromLeaf(self, node: TreeNode) -> str:
        self.result = 'z' * 10000
        self._helper(node, '')
        return self.result

    def _helper(self, node, prefix):
        if node is None:
            return
        prefix = string.ascii_lowercase[node.val] + prefix
        if node.left:
            self._helper(node.left, prefix)
        if node.right:
            self._helper(node.right, prefix)
        if node.left is None and node.right is None:
            self.result = min(prefix, self.result)