LC-0988 Medium LeetCode

988. Smallest String Starting From Leaf

String Backtracking Tree Depth-First Search Binary Tree

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 61% Topics: String, Backtracking, Tree, Depth-First Search, Binary Tree

Reading material

Strings 12 min Backtracking 14 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n + l * h), l is the number of leaves
# Space: O(h)

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


class Solution(object):
    def smallestFromLeaf(self, root):
        """
        :type root: TreeNode
        :rtype: str
        """
        def dfs(node, candidate, result):
            if not node:
                return

            candidate.append(chr(ord('a') + node.val))
            if not node.left and not node.right:
                result[0] = min(result[0], "".join(reversed(candidate)))
            dfs(node.left, candidate, result)
            dfs(node.right, candidate, result)
            candidate.pop()

        result = ["~"]
        dfs(root, [], result)
        return result[0]

Solution from kamyu104/LeetCode-Solutions · MIT