988.smallest-string-starting-from-leaf.md

988. Smallest String Starting From Leaf

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

private var result: String? = null

fun smallestFromLeaf(root: TreeNode?): String {
    if (root == null) return ""
    val path = ArrayDeque<Char>()
    dfs(root, path)
    return result!!
}

private fun dfs(root: TreeNode, path: ArrayDeque<Char>) {
    path.addFirst(intToChar(root.`val`))
    if (root.left == null && root.right == null) {
        compare(path.joinToString(""))
    }
    if (root.left != null) dfs(root.left, path)
    if (root.right != null) dfs(root.right, path)
    path.removeFirst()
}

private fun intToChar(value: Int): Char = 'a' + value

private fun compare(str: String) {
    if (result == null || (result != null && str.compareTo(result!!) < 0)) result = str
}

• Time Complexity: O(n).
• Space Complexity: O(n).