LeetCode 题解工作台
从叶结点开始的最小字符串
给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z' 。 返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束 。 注 ： 字符串中任何较短的前缀在 字典序上 都是 较小 的： 例如，在字典序上 "ab"…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
class Solution: def smallestFromLeaf(self, root: TreeNode) -> str:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。
返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
注：字符串中任何较短的前缀在 字典序上 都是 较小 的：
- 例如，在字典序上
"ab"比"aba"要小。叶结点是指没有子结点的结点。
节点的叶节点是没有子节点的节点。
示例 1：
输入：root = [0,1,2,3,4,3,4] 输出："dba"
示例 2：
输入：root = [25,1,3,1,3,0,2] 输出："adz"
示例 3：
输入：root = [2,2,1,null,1,0,null,0] 输出："abc"
提示：
- 给定树的结点数在
[1, 8500]范围内 0 <= Node.val <= 25
解题思路
方法一
# 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: TreeNode) -> str:
ans = chr(ord('z') + 1)
def dfs(root, path):
nonlocal ans
if root:
path.append(chr(ord('a') + root.val))
if root.left is None and root.right is None:
ans = min(ans, ''.join(reversed(path)))
dfs(root.left, path)
dfs(root.right, path)
path.pop()
dfs(root, [])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot n) |
| 空间 | O(n \cdot n) |
面试官常问的追问
外企场景- question_mark
Check if the candidate correctly reverses paths from leaf to root before comparison.
- question_mark
Observe if the candidate uses backtracking to manage path state efficiently.
- question_mark
Notice whether the solution handles lexicographical comparison accurately at each leaf.
常见陷阱
外企场景- error
Failing to reverse the path string before comparing leaf-to-root strings, yielding incorrect lexicographical order.
- error
Modifying a shared path string without proper backtracking, causing sibling path evaluation errors.
- error
Comparing incomplete paths or intermediate nodes instead of strictly leaf-to-root paths.
进阶变体
外企场景- arrow_right_alt
Compute the largest string from leaf to root using the same DFS and backtracking framework.
- arrow_right_alt
Return the smallest string starting from a specific leaf instead of all leaves, requiring targeted path tracking.
- arrow_right_alt
Handle n-ary trees instead of binary trees, adapting DFS and path management to multiple children.