§1
题目描述
给定二叉树 root，节点值 0..25 对应 a..z。对每个叶子，取「叶子→根」路径上的字母组成字符串，返回字典序最小的一个。
输入 = root=[0,1,2,3,4,3,4] 输出 = "dba"
§2
思路解析动画文字版
记住「下行追加、到叶成串比最小、回溯弹出」，下面每帧都在套它。
准备 · 空路径
开局路径为空、最小串还没有。DFS 从根出发，沿左右孩子一路下探到每个叶子。
下行 · 访问 a
走到节点 a（紫色），把它追加进当前路径，现在根到这里是 a。它还有孩子，继续往下走。
下行 · 访问 b
走到节点 b（紫色），把它追加进当前路径，现在根到这里是 ab。它还有孩子，继续往下走。
下行 · 访问 d
走到节点 d（紫色），把它追加进当前路径，现在根到这里是 abd。它没有孩子，是个叶子。
到达叶子 d。把路径反过来（叶→根）拼成候选串 “dba”。它比之前的最小串更小，刷新最小为 dba。
回溯 · 离开 d
节点 d 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
下行 · 访问 e
走到节点 e（紫色），把它追加进当前路径，现在根到这里是 abe。它没有孩子，是个叶子。
到达叶子 e。把路径反过来（叶→根）拼成候选串 “eba”。它不比当前最小 dba 小，保持不变。
回溯 · 离开 e
节点 e 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
回溯 · 离开 b
节点 b 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
下行 · 访问 c
走到节点 c（紫色），把它追加进当前路径，现在根到这里是 ac。它还有孩子，继续往下走。
下行 · 访问 d
走到节点 d（紫色），把它追加进当前路径，现在根到这里是 acd。它没有孩子，是个叶子。
到达叶子 d。把路径反过来（叶→根）拼成候选串 “dca”。它不比当前最小 dba 小，保持不变。
回溯 · 离开 d
节点 d 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
下行 · 访问 e
走到节点 e（紫色），把它追加进当前路径，现在根到这里是 ace。它没有孩子，是个叶子。
到达叶子 e。把路径反过来（叶→根）拼成候选串 “eca”。它不比当前最小 dba 小，保持不变。
回溯 · 离开 e
节点 e 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
回溯 · 离开 c
节点 c 的子树都试完了，回溯：把它从路径里弹出（标蓝表示已处理），回到它的父节点继续。
根节点 a 的左右子树都试完了，把它从路径弹出，DFS 到此全部结束——所有根到叶的路径都比过了。
完成
四个叶子分别给出 dba、eba、dca、eca，字典序最小的是 “dba”，就是答案。整个过程一次 DFS、回溯时弹出，路径始终保持「根到当前」。
边界先想清：单节点直接成串；左右叶子各自「叶→根」成串后取最小。
面试重点：解释为什么「叶→根」不能简单前缀剪枝。
§3
参考代码
from typing import Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def smallestFromLeaf(self, root: Optional[TreeNode]) -> str: best = None def dfs(node, path): nonlocal best if not node: return path.append(chr(ord('a') + node.val)) if not node.left and not node.right: cand = ''.join(reversed(path)) if best is None or cand < best: best = cand else: dfs(node.left, path) dfs(node.right, path) path.pop() dfs(root, []) return best or ''看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。
§4
复杂度
- 时间：O(n+ΣL)，最坏 O(nh)，遍历 O(n)；每个叶子反转/拼/比较串长 O(h)；叶子又多又深(如梳子形树)时累加可达 O(n²)
- 空间：O(h)，递归栈深 + 当前路径，均为树高 h（最坏 O(n)）
§5
易错点
✗ 错误写法：直接用「根→叶」方向比较
✓ 正确写法：题目要「叶→根」，要把路径反转
方向反了字典序结果完全不同
✗ 错误写法：回溯时忘了 path.pop()
✓ 正确写法：离开节点必须弹出
不弹出会污染兄弟分支的路径
✗ 错误写法：用根到叶的前缀比较来剪枝
✓ 正确写法：本题不能简单按前缀剪枝
因为比较的是反转串，短前缀小不代表整串小
§
面试追问把动画讲成自己的话
追问能不能像比较「根→叶」那样边走边剪枝？
不能简单剪。因为比较的是「叶→根」反转串，路径越深，新加的字母排在串的越前面（更高位），会改变整个字典序。所以必须走到叶子、拼出完整候选再比较，不能靠根侧前缀提前判断。
追问如何降低拼接/比较成本？
可以维护一个可变字符数组，下行 push、回溯 pop；到叶子时再反转比较。也可以用「按字符逐位比较 best」的方式避免每次都构造完整字符串，但实现更复杂，面试讲清思路即可。
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一题 · 树套路 21/32
→节点与其祖先之间的最大差值
LeetCode 1026 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
599道动画图解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路？去图解算法专题