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

2022-05-13 HGNULB 约 11 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

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

题意分析

一棵二叉树，每个节点的值在 0..25 之间，分别代表字母 a 到 z。对每个叶子节点，把「从该叶子沿父指针走到根」经过的字母连起来得到一个字符串；求所有这些字符串中字典序最小的那一个。

最关键的一处是方向：题目要的是叶到根的字符串，而 DFS 天然产生的是根到叶的路径。这意味着必须在某个环节做反转，不能直接拿根到叶的串去比较——两者的字典序结论完全不同。举个例子，路径 a → b 与 b，根到叶的串是 ab 与 b，ab 更小；但叶到根的串是 ba 与 b，此时 b 更小。方向搞反会得到相反的答案。

第二处是字典序的前缀规则：当一个串是另一个串的前缀时，短的更小。这条规则在本题里会真实触发——叶子深度不同的两条路径可能一个是另一个的前缀。好消息是各语言内置的字符串比较（Java 的 compareTo、Go 的 <）已经正确实现了这一规则，直接用即可，不必手写逐字符比较。

第三处是「叶子」的定义：左右孩子都为空才算叶子。只有一个孩子的节点不是叶子，不能在它那里结算答案——这是本题最高频的边界错误，因为单孩子节点在很多树题里会被当成「路径尽头」。

约束里节点数不超过 8500，节点值在 0..25。规模不大，允许每到一个叶子就构造一次字符串并比较，即使最坏情况下总代价是 $O(n^2)$ 级别也能通过；这说明本题考的是路径回溯与方向处理，而不是极致效率。

边界方面：树至少有一个节点，不必考虑空树（但代码里保留空判断更稳）；答案初值用空串配合「空则直接接受」的判断，可以避免为「第一个叶子」写特判。

解法：DFS 回溯 + 叶子处倒序生成字符串

核心思路

最朴素的想法是先把所有根到叶路径全部收集进一个列表，再逐条反转、排序取最小。这能出正确答案，但要额外存下所有路径，空间浪费；而且排序是多余的——只求最小值，边走边比即可。

瓶颈其实不在算法而在路径的维护方式。如果每进入一个节点就新建一个字符串做拼接，那么每层都会复制一次整条路径，代价是 $O(深度)$ 的复制，总开销会被显著放大。正确的做法是用一个可变缓冲区配合回溯：进入节点时在末尾追加字符，离开节点时把这个字符删掉。缓冲区在整个 DFS 过程中只有一份，任何时刻它的内容恰好是「根到当前节点」的路径。

这就是维持的不变量：dfs(node) 执行期间，缓冲区的内容始终等于从根到 node 的字母序列；函数返回时缓冲区必须恢复成进入前的样子。追加与删除严格配对，这个不变量才能在整棵树上成立。

关于方向，有两种处理办法。一种是每次在缓冲区头部插入字符，这样缓冲区直接就是「当前节点到根」的顺序，到叶子时可以直接取用；但头插会导致后面所有字符整体后移，每次 $O(深度)$，性能反而更差。另一种是本文采用的做法：缓冲区按正常顺序（根到叶）追加，只在到达叶子时才倒序生成一次字符串。因为只有叶子才需要完整的串，而内部节点根本不需要，所以把反转推迟到叶子是更省的选择。

比较与更新则很直接：维护一个 best，每得到一个叶子串就与它比较，更小则替换。初值取空串并约定「best 为空时无条件接受」，这样第一个叶子自然被收下，不需要额外的「是否首次」标志。

最后要强调结算的位置：只在叶子处结算。内部节点即使字符更小也不能参与比较，因为它不构成一条完整的「叶到根」路径。

解题步骤

准备答案变量与路径缓冲区：best 初始化为空串，缓冲区初始为空。为什么 best 用空串而不是某个「无穷大」的哨兵串：空串配合显式的空判断更直观，也避免了构造哨兵时猜测最大长度。

递归基：node == null 直接返回。为什么需要它：内部节点可能只有一个孩子，另一侧递归会传入空指针；有了这条基，调用方就不必在每次递归前判空。

进入节点：追加字符。char c = 'a' + node.val，追加到缓冲区末尾。为什么是 'a' + val：题目约定 0 对应 a、25 对应 z，这是直接的线性映射。

判断是否叶子：node.left == null && node.right == null。为什么必须两个都判：只有一个孩子的节点还不是路径终点，在它那里结算会得到一条不完整的路径，比如把 b（内部）当叶子会引入本不存在的候选串。

叶子处结算：把缓冲区倒序读出生成字符串，与 best 比较并按需更新。为什么在这里才反转：只有叶子需要完整的串，内部节点反转纯属浪费；而且倒序读取只需一次线性扫描，不影响缓冲区本身。

非叶子则继续递归左右孩子：顺序无所谓，因为最终取的是全局最小值，遍历次序不影响结果。

离开节点：删除末尾字符（回溯）。为什么必须删：缓冲区是全局共享的，如果不还原，兄弟子树会看到本子树遗留的字符，路径全乱。这一步与追加严格配对，是回溯的本质。

返回 best。

以 root = [0,1,2,3,4,3,4] 走一遍，即根 a(0)，左 b(1)、右 c(2)，四个叶子依次是 d(3)、e(4)、d(3)、e(4)。
进入根：缓冲区 a。不是叶子，递归左孩子。
进入节点 b：缓冲区 ab。不是叶子，递归它的左孩子。
进入叶子 d：缓冲区 abd，是叶子，倒序生成 dba；best 为空，直接接受，best = "dba"。回溯删除 d，缓冲区回到 ab。
进入叶子 e：缓冲区 abe，倒序得 eba；与 dba 比较，e > d，不更新。回溯删除 e，缓冲区回到 ab。
从 b 返回：删除 b，缓冲区回到 a。
进入节点 c：缓冲区 ac。两个叶子分别得到 dca 与 eca，都大于 dba（第二个字符 c 大于 b），不更新。回溯后缓冲区回到 a。
从根返回：删除 a，缓冲区清空。返回 "dba"，与预期一致。

再看能体现前缀规则的用例 root = [25,1,3,1,3,0,2]：根是 z(25)，左子树的叶子路径倒序后以 b、b 开头，右子树两个叶子分别得到 adz 与 caz（a 对应 0、c 对应 2）。最小的是 adz。若把方向写反，比较的将是 zba、zdb、zaa、zbc 之类的根到叶串，答案会变成完全不同的串。

代码实现

class Solution {
    private String best = "";

    public String smallestFromLeaf(TreeNode root) {
        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^2)$。凭什么：DFS 本身访问每个节点一次是 $O(n)$；但每到一个叶子都要花 $O(深度)$ 生成字符串并做一次 $O(深度)$ 的字典序比较。叶子数量与树高的乘积在退化成「一条长链挂满叶子」时可达 $O(n^2)$，平衡树下约为 $O(n \log n)$。

空间复杂度：$O(n)$。凭什么：递归栈深度等于树高，最坏为 $O(n)$；路径缓冲区长度同样不超过树高；best 与每次生成的临时串长度也不超过树高。这些都是同阶的，不叠加出更高的量级。

关键点总结

题目要求的字符串方向与 DFS 天然产生的方向相反时，先把这件事说清楚再动手；把反转推迟到叶子处只做一次，比每层头插要省得多。

路径类回溯的骨架永远是「进入时追加、离开时删除」，两步严格配对。判断代码对不对，就看函数返回时缓冲区是否恢复原状。

叶子的判定必须是「左右孩子都为空」。只有一个孩子的节点是内部节点，在那里结算会引入伪路径——这是树上路径题最常见的错误。

字典序的前缀规则（短串更小）由语言内置比较正确实现，直接用 compareTo 或 < 即可，手写逐字符比较反而容易漏掉长度不等的分支。

求最值时用「空值 + 无条件接受」代替「是否首次」的布尔标志，可以少一个变量也少一处分支。

面试视角：开口先点出「叶到根 vs 根到叶」这个方向陷阱，再说明只在叶子结算、内部节点不参与比较，最后提一句「短串是长串前缀时更小，内置比较已覆盖」。这三点讲全，基本就通过了；若被追问优化，可以说可以在下降过程中做剪枝——但由于比较的是反转后的串，前缀剪枝并不直接成立，这一点反而是加分的诚实回答。

易错点总结

错误写法：直接拿根到叶的串比较，不做反转 → 用例 [0,1,2,3,4,3,4] 中比较的是 abd、abe、acd、ace，返回 abd，而正确答案是 dba。

错误写法：把只有一个孩子的节点当叶子（判断写成 node.left == null || node.right == null） → 用例 [2,2,1,null,1,0,null,0] 中内部节点被结算，产生本不存在的候选串，答案从 abc 变成更小的伪串。

错误写法：忘记回溯删除末尾字符 → 用例 [0,1,2,3,4,3,4] 中右子树会带着左子树遗留的字符，缓冲区变成 abdec...，生成的串完全错乱。

错误写法：回溯的删除写在 return 之后或只写在某个分支里 → 用例中叶子分支提前返回时缓冲区没还原，兄弟节点看到脏路径。

错误写法：best 初值设为 "z" 之类的单字符哨兵 → 用例中任何以 z 之后字符开头的合法串都比不过它，但更致命的是长度更长且以 z 开头的串（如 zba）会被误判为更大，答案漏解。

错误写法：best 初值为空串却写成 s.compareTo(best) < 0 而不带空判断 → 空串比任何非空串都小，第一个叶子永远无法被接受，最终返回空串。

错误写法：字符映射写成 'a' + node.val - 1 或直接用 (char) node.val → 用例中 0 被映射成 ` 或不可见字符，比较结果毫无意义。

错误写法：每层新建字符串做 path + c 拼接并当成「更简单的写法」 → 用例节点数 8500 且树退化成链时，每层复制整条路径，总代价升到 $O(n^2)$ 的字符复制，且丢掉了回溯这一考点。

错误写法：在缓冲区头部插入字符以省去反转 → 用例中每次插入都要移动整条路径，深度大时明显更慢；虽然结果正确，但面试中会被追问为什么不推迟到叶子再反转。

错误写法：把所有叶子串收集到列表里再排序取第一个 → 用例中答案正确，但额外占用 $O(叶子数 \times 深度)$ 空间，且排序是多余的，求最小值只需边走边比。

错误写法：递归前不判空，直接访问 node.left.val → 用例 [2,2,1,null,1,...] 中缺失的孩子导致空指针异常（Go 里 nil 解引用 panic）。

错误写法：在内部节点也做一次比较更新 → 用例 [0,1,2,3,4,3,4] 中根节点自己的串 a 会成为候选并胜出，返回 a，而它并不对应任何叶子路径。

相似题目

题目	难度	考察点
257. 二叉树的所有路径	简单	同样的回溯骨架，但要输出全部路径而非取最值，方向也无需反转
129. 求根节点到叶节点数字之和	中等	路径信息可以边下降边累积成数字，无需缓冲区，也就无需回溯
113. 路径总和 II	中等	回溯加剪枝，结算条件是路径和达标，考的是列表的增删配对
112. 路径总和	简单	只需布尔判定，靠递减目标值传参即可，是路径类里最轻的一档
1022. 从根到叶的二进制数之和	简单	用位移在下降时维护数值，展示了「参数传状态」替代「缓冲区回溯」的写法
437. 路径总和 III	中等	路径起点不必是根，需要前缀和加哈希表，回溯的对象从字符变成计数
124. 二叉树中的最大路径和	困难	路径可跨越节点左右两侧，靠返回值与全局变量分工，而不是显式路径缓冲