Algorithm
Problem Name: 988. Smallest String Starting From Leaf
You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.
Return 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: root = [0,1,2,3,4,3,4] Output: "dba"
Example 2:
Input: root = [25,1,3,1,3,0,2] Output: "adz"
Example 3:
Input: root = [2,2,1,null,1,0,null,0] Output: "abc"
Constraints:
- The number of nodes in the tree is in the range
[1, 8500]. 0 <= Node.val <= 25
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String smallestFromLeaf(TreeNode root) {
return dfs(root, "");
}
private String dfs(TreeNode root, String curr) {
if (root == null) {
return curr;
}
curr = "" + (char)(97 + root.val) + curr;
if (root.left == null && root.right == null) {
return curr;
} else if (root.left == null || root.right == null) {
return root.left == null ? dfs(root.right, curr) : dfs(root.left, curr);
} else {
String left = dfs(root.left, curr);
String right = dfs(root.right, curr);
return left.compareTo(right) < = 0 ? left : right;
}
}
}
Input
root = [0,1,2,3,4,3,4]
Output
"dba"
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const smallestFromLeaf = function(root) {
const res = []
chk(root, [], res)
res.sort()
return res[0]
};
function chk(node, path, res) {
if(node == null) return
path.push(node.val)
if(node.left == null && node.right == null) {
res.push(arrToStr( path.slice(0).reverse() ))
return
}
chk(node.left, path.slice(0), res)
chk(node.right, path.slice(0), res)
}
function numToChar(num) {
const str = 'abcdefghijklmnopqrstuvwxyz'
return str[num]
}
function arrToStr(arr) {
let res = ''
for(let i = 0; i < arr.length; i++) {
res += numToChar(arr[i]>
}
return res
}
Input
root = [0,1,2,3,4,3,4]
Output
"dba"
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def smallestFromLeaf(self, root: TreeNode, s = '') -> str:
if not root.right and not root.left:
return chr(97 + root.val) + s
if not root.right:
return self.smallestFromLeaf(root.left, chr(97 + root.val) + s)
if not root.left:
return self.smallestFromLeaf(root.right, chr(97 + root.val) + s)
return min(self.smallestFromLeaf(root.left, chr(97 + root.val) + s), self.smallestFromLeaf(root.right, chr(97 + root.val) + s))
Input
root = [25,1,3,1,3,0,2]
Output
"adz"