988. Smallest String Starting From Leaf

Description

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:

Constraints:

• The number of nodes in the tree is in the range [1, 8500].
• 0 <= Node.val <= 25

C++

使用 dfs 往下找到 leaf 節點再計算他的字串比較，原本想要使用中止條件 if (!node) return; 作為比較字串的地方，但是發現在很多情況不適用。直接使用 if (!node->left && !node->right) 較為恰當。
tmp.erase(0, 1) 用來刪除字串第一項。
我認為這方法不錯，可以進 beats 100%

class Solution {
public:
    char intToChar(int value) {
        return 'a' + value;  
    }
    void dfs (TreeNode *node, string &min, string &tmp) {
        if (!node) return;
        tmp = intToChar(node->val) + tmp;
        if (!node->left && !node->right) {
            if (min.empty() || tmp < min) {
                min = tmp; 
            }
        } else {
            dfs(node->left, min, tmp);
            dfs(node->right, min, tmp); 
        }
    
        tmp.erase(0, 1);
    }
    string smallestFromLeaf(TreeNode* root) {
        string min = "";
        string tmp = "";
        dfs(root, min, tmp);
        return min;
    }
};

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        def dfs(node, temp, minimum):
            if not node:
                return
            temp = chr(ord("a") + node.val) + temp
            if not node.left and not node.right:
                minimum[0] = min(minimum[0], temp)

            dfs(node.left, temp, minimum)
            dfs(node.right, temp, minimum)

        minimum = [chr(ord("z") + 1)]
        dfs(root, "", minimum)

        return minimum[0]