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
}