LeetCode 988. 从叶结点开始的最小字符串
题目描述
题意分析
节点值
0到25对应字母a到z。每个叶子到根的路径形成一个候选字符串，求其中字典序最小的完整字符串；只有左右孩子都为空的节点才是叶子。比较从叶子一端开始，而遍历通常从根开始，因此不能根据根附近的字符提前选定某个分支。需要完整到达叶子，再按题目要求的方向比较。
解法：路径递归 + 叶子倒序比较
核心思路
[!blue]
用深度优先搜索枚举叶子，
path保存根到当前节点的字符序列。进入节点时追加当前字符，走到叶子时倒序读取整条路径，就得到它对应的叶到根字符串。每个叶子都被访问一次，所以所有合法候选都会参与比较；内部节点不能作为候选，否则就改变了路径必须从叶子开始的要求。
best保存已经检查过的最小候选。第一次遇到叶子时，空的best只表示尚无答案，要直接接收该候选；之后使用字符串字典序比较更新。比较会从第一个不同字符决定大小，若一个字符串是另一个的完整前缀，则较短者更小，语言自带的字符串比较已经符合这个规则。Java 的递归调用共享同一个
StringBuilder，所以当前节点处理结束后必须删除自己追加的最后一个字符，使父调用重新看到原来的路径。叶子更新答案后也要执行这一步，不能提前返回而留下多余字符。Go 传递的是切片头的副本，子调用追加后改变的是自己的长度，父调用仍保留原长度。即使底层数组共享，追加也只会写到父路径有效前缀之后；访问兄弟分支时从同一前缀继续追加即可，不需要手动缩短父切片。生成候选时使用独立的倒序缓冲，不反转共享路径，因此后续遍历也不会改坏当前路径或已保存答案。
解题步骤
- 每次调用初始化空答案。
- 递归进入节点时追加对应字母。
- 叶子处倒序生成完整候选并更新最小值。
- 继续其他分支，Java 返回前恢复共享路径长度。
只有根节点时，根本身就是叶子，返回它对应的一个字符；只有一个孩子的节点仍要向下搜索。Java 把
best存为成员变量，因此每次公开调用都重新清空；Go 的best是本次调用的局部变量，不会残留上一棵树的结果。
代码实现
class Solution {
private String best = "";
public String smallestFromLeaf(TreeNode root) {
// 每次调用重新选择答案，避免前一棵树的结果残留。
best = "";
dfs(root, new StringBuilder());
return best;
}
private void dfs(TreeNode node, StringBuilder path) {
if (node == null) {
return;
}
path.append((char) ('a' + node.val));
// 左右都为空才是叶子，只有叶子才构成完整的「叶到根」路径。
if (node.left == null && node.right == null) {
String s = reverseToString(path);
if (best.isEmpty() || s.compareTo(best) < 0) {
best = s;
}
} else {
dfs(node.left, path);
dfs(node.right, path);
}
// 回溯：与上面的 append 严格配对，还原缓冲区。
path.deleteCharAt(path.length() - 1);
}
private String reverseToString(StringBuilder path) {
int n = path.length();
char[] chars = new char[n];
for (int i = 0; i < n; i++) {
chars[i] = path.charAt(n - 1 - i);
}
return new String(chars);
}
}
func smallestFromLeaf(root *TreeNode) string {
best := ""
var dfs func(node *TreeNode, path []byte)
dfs = func(node *TreeNode, path []byte) {
if node == nil {
return
}
path = append(path, byte('a'+node.Val))
// 左右都为空才是叶子，只有叶子才构成完整的「叶到根」路径。
if node.Left == nil && node.Right == nil {
reversed := reverseBytes(path)
s := string(reversed)
if best == "" || s < best {
best = s
}
return
}
// 子调用接收自己的切片长度，父层长度不变，兄弟分支从同一前缀追加。
dfs(node.Left, path)
dfs(node.Right, path)
}
dfs(root, []byte{})
return best
}
func reverseBytes(b []byte) []byte {
n := len(b)
out := make([]byte, n)
for i := 0; i < n; i++ {
out[i] = b[n-1-i]
}
return out
}
复杂度分析
- 时间复杂度：$O(n+Σd)$，Σd 为所有叶子路径长度之和，最坏 $O(nh)$，h 为树高。
- 空间复杂度：$O(h)$ 辅助上界，保存路径、递归栈与候选字符串。
关键点总结
[!green]
- 只在叶子处比较，方向必须从叶到根。
- Java 共享缓冲需要恢复，Go 切片长度传递不能套用相同删除说明。
- 每次公开调用重新开始答案，避免前一次结果残留。
易错点总结
[!yellow]
- 直接比较根到叶路径：字典序方向不同。
- 有一个孩子为空就判作叶子：单孩子内部节点也被当作候选。
- Java 提前返回而没有恢复路径：兄弟分支继承脏内容。
- 空答案不作首次接收处理：任何非空候选都无法小于空串。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 257. 二叉树的所有路径 | 简单 | 同样枚举根到叶路径，本题在叶子处按反向的叶到根字符串比较，不能只比较根侧前缀。 |
| 129. 求根节点到叶节点数字之和 | 中等 | 同样沿路径累积数据，原题按根到叶形成数值，本题比较方向相反。 |