难度：★★★☆☆
类型：树
方法：深度优先搜索

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。

找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）

示例 1：

输入：[0,1,2,3,4,3,4]
输出："dba"

示例 2：

输入：[25,1,3,1,3,0,2]
输出："adz"

示例 3：

输入：[2,2,1,null,1,0,null,0]
输出："abc"

提示：

给定树的结点数介于 1 和 8500 之间。
树中的每个结点都有一个介于 0 和 25 之间的值。

解答

我们可以通过深度优先搜索的方法探索每一条路径，选取并比较字典序最小的字符串作为结果返回。需要注意的是：

结果需要初始化为一个较大字典序的字符串；

深度优先搜索的递归函数的终止条件是检测到叶子节点；

使用一个列表用来保存当前路径下遍历到的各个结点。

class Solution:
    def smallestFromLeaf(self, root):
        self.ans = chr(ord("z") + 1)

        def val2chr(val):
            return chr(val + ord("a"))

        def dfs(node, arr):
            if node:
                arr.append(val2chr(node.val))
                if not node.left and not node.right:
                    self.ans = min(self.ans, "".join(reversed(arr)))

                dfs(node.left, arr)
                dfs(node.right, arr)
                arr.pop()

        dfs(root, [])
        return self.ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析