988. Smallest String Starting From Leaf
Meidum
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
Runtime: 3 ms, faster than 100%
Memory Usage: 4.5 MB, less than 92%
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func smallestFromLeaf(root *TreeNode) string {
return helper(root, "")
}
func helper(root *TreeNode, str string) string {
if root == nil {
return str
}
newStr := string(byte(root.Val + 97)) + str
if root.Left == nil && root.Right == nil {
return newStr
}
if root.Left == nil {
return helper(root.Right, newStr)
}
if root.Right == nil {
return helper(root.Left, newStr)
}
return min(helper(root.Left, newStr), helper(root.Right, newStr))
}
func min(a, b string) string{
if a < b {
return a
}
return b
}