998 Smallest String Starting From Leaf

Problem Setting

The 2nd problem in Weekly Contest 122 is Smallest String Starting From Leaf

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find 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.)

Solution from Hey Shao

reference: Hey Shao's solution: https://leetcode.com/hanshaohey/

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

def smallestFromLeaf(root):
    :type root: TreeNode
    :rtype: str
    for i,l in enumerate(letters):
    def helper(node):
        if not node.left and not node.right:
            return maps[node.val]
        elif not node.left:
            return helper(node.right)+maps[node.val]
        elif not node.right:
            return helper(node.left)+maps[node.val]
            return min(l+ll,r+ll)
    return helper(root)

Step-by-step solution

Now I am going to break down the problem and solve it step-by-step. First of all, we are aiming to pass the easiest example as below.

Example 1)

  • Input: [0,1,2,3,4,3,4]
  • Output: "dba"

Create mapping from integer to alphabet

this is used to convert the integer to alphabet.

In [6]:
# My solution
import string
d = {}
for x, y in zip(range(0, 26), string.ascii_lowercase):
    d[x] = y

# Hao's solution
for i,l in enumerate(letters):
In [3]:
In [4]:

Recursive function

Now we need to create the recursive function which returns the strings associated to the shortest path by given a node or tree. There are 4 cases for each node:

  1. both node is null
  2. left node is null
  3. right note is null
  4. both node has another tree

For cases 1~3, it is obvious to determine what is the shortest path for the given node. For case 4, we need to see which is the shortest based on the returned string from both node, which requires calling the recursive function.

Learning - min with string

We do not have to store the length and string at the same time. If we pass two strings to min function, the function returns the shorter one. For example,

In [7]:
min('abc', 'xyzxyz')


Input: [0,1,2,3,4,3,4]

In [8]:
root = TreeNode(0)
root.left = TreeNode(1)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(4)
In [11]:


This is the problem we need to use

  • mapping dictionary from integer to alphabet
  • recursive function to return the strings matched with the shorted path
  • implement 4 possible cases for each node


Comments powered by Disqus