从叶结点开始的最小字符串

🎯 问题描述（来源于LeetCode）

描述：
给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。
返回按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

说明：

  • 字符串中任何较短的前缀在字典序上都是较小的（例如 "ab" 比 "aba" 小）。

  • 叶结点是指没有子结点的结点。

  • 示例：

    • 示例 1：
      1
      2
      输入：root = [0,1,2,3,4,3,4]
      输出："dba"
    • 示例 2：
      1
      2
      输入：root = [25,1,3,1,3,0,2]
      输出："adz"

💻 解题思路

思路：DFS 深度优先搜索（路径拼接与反转）

代码实现

from typing import Optional

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        ans = "~"  # 初始化为一个比 'z' 大的字符作为基准
        
        def dfs(node, path):
            if not node:
                return
            
            # 1. 将当前节点的值转换为字符，并拼接到路径中
            path += chr(ord("a") + node.val)
            
            nonlocal ans
            # 2. 如果是叶子节点，说明找到了一条完整的路径
            if not node.left and not node.right:
                # 题目要求从叶到根，所以需要将收集到的路径反转
                current_str = path[::-1]
                # 更新字典序最小的字符串
                if current_str < ans:
                    ans = current_str
            
            # 3. 继续向左右子树遍历
            dfs(node.left, path)
            dfs(node.right, path)
        
        dfs(root, "")
        return ans

📊 性能分析

  • 时间复杂度：O(N⋅H)O(N \cdot H)。其中 NN 是节点数，HH 是树的高度。每个节点访问一次，但在叶子节点处进行字符串反转和比较操作，字符串长度最大为树高 HH。
  • 空间复杂度：O(H)O(H)。递归调用栈的深度以及存储路径字符串的空间，取决于二叉树的高度。

💡 思考

这道题是二叉树 DFS 与字符串处理的结合。核心在于：

  1. 路径收集：在 DFS 过程中，通过参数 path 向下传递从根节点到当前节点的路径。
  2. 方向转换：题目要求“叶 -> 根”，而 DFS 天然顺序是“根 -> 叶”。因此，在到达叶子节点时，需要对收集到的路径进行反转操作。
  3. 字典序比较：利用 Python 字符串可以直接比较大小的特性，动态维护全局的最小字符串。