Formatted question description: https://leetcode.ca/all/988.html

988. Smallest String Starting From Leaf

Level

Medium

Description

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

Example 1:

Image text

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

Output: “dba”

Example 2:

Image text

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

Output: “adz”

Example 3:

Image text

Input: [2,2,1,null,1,0,null,0]

Output: “abc”

Note:

  1. The number of nodes in the given tree will be between 1 and 8500.
  2. Each node in the tree will have a value between 0 and 25.

Solution

Do breadth first search. Initially, for each node, the string is reversed, which means the string starts from root and ends at the current node. If a leaf is met, reverse the string and update the smallest string starting from leaf. Finally, return the smallest string.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    String smallestStr = "";

    public String smallestFromLeaf(TreeNode root) {
        if (root == null)
            return smallestStr;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<StringBuffer> strQueue = new LinkedList<StringBuffer>();
        nodeQueue.offer(root);
        strQueue.offer(new StringBuffer(String.valueOf((char) ('a' + root.val))));
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            StringBuffer sb = strQueue.poll();
            TreeNode left = node.left, right = node.right;
            if (left == null && right == null) {
                sb.reverse();
                String str = sb.toString();
                if (smallestStr.length() == 0 || str.compareTo(smallestStr) < 0)
                    smallestStr = str;
                sb.reverse();
            } else {
                if (left != null) {
                    StringBuffer leftSB = new StringBuffer(sb.toString());
                    leftSB.append((char) ('a' + left.val));
                    nodeQueue.offer(left);
                    strQueue.offer(leftSB);
                }
                if (right != null) {
                    StringBuffer rightSB = new StringBuffer(sb.toString());
                    rightSB.append((char) ('a' + right.val));
                    nodeQueue.offer(right);
                    strQueue.offer(rightSB);
                }
            }
        }
        return smallestStr;
    }
}

All Problems

All Solutions