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

988. Smallest String Starting From Leaf

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:

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

Output: “dba”

Example 2:

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

Example 3:

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;
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;
}
}