LeetCode 872. 叶子相似的树

2026-03-28 HGNULB 约 9 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 872. 叶子相似的树

题意分析

题目目标：把一棵二叉树从左到右的所有叶子节点的值依次连起来，得到「叶值序列」。判断两棵树的叶值序列是否完全相同。

核心约束：注意是序列而不是集合——顺序必须一致，重复值也必须出现同样的次数，所以不能用哈希集合、求和或排序后比较来偷懒。「从左到右」这个顺序，对应的正是任意一种保持左子树先于右子树的深度优先遍历（前序、中序、后序都行，因为叶子在这三种遍历中的相对先后顺序相同）。

边界处理：只有一个节点的树，根本身就是叶子；节点值可以是 0，所以不能用 0 当哨兵；两棵树的节点数可以差很多，但只要叶值序列相同就算相似；两个序列长度不同必须直接判为不同。

实现取舍：可以分别收集两个序列再比较（写法直白，$O(L)$ 额外空间），也可以用两个迭代器交替产出叶子做流式比较（空间降到 $O(h)$，但要手写显式栈）。面试里先给前者，把后者作为「如果树大到装不下叶值序列怎么办」的追问答案。

解法：深度优先搜索

核心思路

题目问的是两棵树的关系，但两棵树之间没有任何结构上的对应——它们的形状可以完全不同。所以不能像「相同的树」那样同步递归比较，唯一可行的路径是：先把每棵树各自压缩成一个与形状无关的特征（叶值序列），再比较两个特征。这一步「把结构问题降维成序列问题」是全题的核心。

剩下的问题是怎么按「从左到右」的顺序收集叶子。观察一下：只要递归时先进左子树、后进右子树，叶子被访问到的先后顺序就一定是从左到右的；至于父节点是在孩子之前还是之后被处理（前序还是后序），完全不影响叶子之间的相对顺序，因为父节点根本不是叶子、不会进入序列。所以不必纠结用哪种遍历。

于是不变量是：dfs(node, nums) 执行完毕后，nums 末尾追加的正是以 node 为根的子树中所有叶子的值，且顺序为从左到右。递归的语义就这一句，父调用只管按「先左后右」的顺序拼接子调用的结果。

叶子的判定用了一个小技巧：root.left == root.right。在二叉树里，一个节点的左右孩子指针相等当且仅当两者都为 null（两个不同的子节点不可能是同一个对象），所以这一条比较等价于 root.left == null && root.right == null，但只写一次比较。

最后是序列比较。必须逐位比较值，先比长度再比元素——长度不同直接判否，这一步同时也避免了越界。

解题步骤

第一步：为两棵树各准备一个列表，分别调用 dfs 收集叶值。 为什么必须收集完再比：两棵树的形状无关，没法同步推进递归；只有把它们各自「拍平」成序列，才有共同的比较基准。

第二步：dfs 里先判 root.left == root.right，成立就把 root.val 追加进列表并返回。 为什么这个判据等价于「是叶子」：见上文，两个孩子指针相等只可能是都为空。为什么判到叶子就返回：叶子没有子树可以继续下探，继续递归会访问空指针。

第三步：否则先递归左孩子（若非空），再递归右孩子（若非空）。 为什么要各自判空：走到这里说明至少有一个孩子非空，但可能只有一个；不判空就会对 null 调用 dfs 并在第一行访问 root.left 时崩溃。为什么顺序不能颠倒：左右顺序直接决定叶值序列的顺序，反过来就是「从右到左」，与题意不符。

第四步：比较两个列表。先看长度是否相等，再逐位比较元素值。 为什么不用集合或排序：题目要的是序列相等，[1,2] 与 [2,1]、[1,1,2] 与 [1,2] 都必须判为不同，而集合和排序都会抹掉这些差别。

以 root1 = [3,5,1,6,2,9,8,null,null,7,4] 与 root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8] 走一遍：

先看 root1 的形状：根 3，左孩子 5、右孩子 1；5 的左孩子 6、右孩子 2；2 的左孩子 7、右孩子 4；1 的左孩子 9、右孩子 8。

dfs(3)：3.left = 5、3.right = 1，两者不等，不是叶子。先递归左孩子 5。dfs(5)：孩子是 6 和 2，不是叶子，先递归 6。dfs(6)：6.left 与 6.right 都是 null，相等，判定为叶子，追加 6 → 列表 [6]。回到 5，递归右孩子 2。dfs(2)：孩子是 7 和 4，不是叶子，先递归 7 → 追加 7 → [6,7]；再递归 4 → 追加 4 → [6,7,4]。5 这一支结束。

回到 3，递归右孩子 1。dfs(1)：孩子是 9 和 8，先递归 9 → 追加 9 → [6,7,4,9]；再递归 8 → 追加 8 → [6,7,4,9,8]。root1 的叶值序列是 [6,7,4,9,8]。

再看 root2：根 3，左孩子 5、右孩子 1；5 的左孩子 6、右孩子 7；1 的左孩子 4、右孩子 2；4 是叶子？按给定的层序，5 的孩子是 6 和 7（都是叶子），1 的孩子是 4 和 2，其中 4 是叶子，2 的孩子是 9 和 8。同样按「先左后右」收集：6 → 7 → 4 → 9 → 8，得到 [6,7,4,9,8]。

两个序列长度都是 5，逐位比较 6=6、7=7、4=4、9=9、8=8，全部相等，返回 true。注意两棵树的形状明显不同（root1 里 7 和 4 挂在 5 的子树下，root2 里挂在不同位置），但叶值序列一致——这正说明了「先降维再比较」的必要性。

再看一个反例 root1 = [1,2,3]、root2 = [1,3,2]：前者叶值序列是 [2,3]，后者是 [3,2]，长度相同但第一位就不等，返回 false。这个用例说明了为什么不能排序后再比。

代码实现

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        dfs(root1, l1);
        dfs(root2, l2);
        return l1.equals(l2);
    }

    private void dfs(TreeNode root, List<Integer> nums) {
        if (root.left == root.right) {
            nums.add(root.val);
            return;
        }
        if (root.left != null) {
            dfs(root.left, nums);
        }
        if (root.right != null) {
            dfs(root.right, nums);
        }
    }
}

func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
    l1, l2 := []int{}, []int{}
    var dfs func(*TreeNode, *[]int)
    dfs = func(root *TreeNode, nums *[]int) {
        if root.Left == root.Right {
            *nums = append(*nums, root.Val)
            return
        }
        if root.Left != nil {
            dfs(root.Left, nums)
        }
        if root.Right != nil {
            dfs(root.Right, nums)
        }
    }
    dfs(root1, &l1)
    dfs(root2, &l2)
    if len(l1) != len(l2) {
        return false
    }
    for i, v := range l1 {
        if v != l2[i] {
            return false
        }
    }
    return true
}

复杂度分析

时间复杂度：$O(n_1 + n_2)$。凭什么：两次深度优先遍历各访问自己那棵树的每个节点恰好一次，节点内只做常数次判断与追加；最后的序列比较不超过叶子总数，被遍历开销吸收。

空间复杂度：$O(h_1 + h_2 + L)$，其中 $h$ 为树高、$L$ 为叶子数。凭什么：递归栈的深度等于树高，最坏情况下树退化成链则为 $O(n)$；两个叶值列表合计存放 $L$ 个整数。若改成两个迭代器交替比较，可以去掉 $L$ 这一项。

关键点总结

两棵结构无关的树要比较，先各自降维成序列，再比序列。 「同步递归」只适用于形状必须一致的题（如 100 相同的树），本题形状可以完全不同，同步递归无从下手。

「从左到右」的叶子顺序由「先递归左子树」保证，与前序/中序/后序的选择无关。 想清楚这一点就不必纠结遍历方式。

root.left == root.right 是判断叶子的等价简写。 两个孩子指针只可能同时为 null 时相等，比写两个 == null 更紧凑。

递归下探前要各自判空。 本题的 dfs 假定入参非空（第一行就访问 root.left），所以调用方必须保证；判空写在调用点而不是函数入口，是这份代码的约定，改动时要保持一致。

序列相等必须逐位比较，不能用集合、排序或求和。 [1,2] 与 [2,1]、[1,1] 与 [1] 的区分全靠这一点。

面试视角：先点明「两棵树形状无关 → 必须降维成序列」，再写收集与比较。面试官常见追问是「树非常大、叶值序列放不下怎么办」——答案是把递归改成显式栈，做成两个惰性迭代器交替吐出叶子并即时比较，空间从 $O(L)$ 降到 $O(h)$，一旦出现不等立刻返回，还能提前终止。

易错点总结

错误写法：把叶值放进 HashSet 再比较集合 → 用例 root1 = [1,2,3]、root2 = [1,3,2]，两个集合都是 {2,3}，返回 true，而期望 false。

错误写法：把两个序列排序后再比较 → 用例同上，排序后都是 [2,3]，返回 true，同样漏判顺序差异。

错误写法：只比较叶值之和或异或值 → 用例 root1 叶值 [1,4]、root2 叶值 [2,3]，和都是 5，返回 true，而两者显然不同。

错误写法：先递归右孩子再递归左孩子 → 用例 root1 = [1,2,3]，收集到 [3,2] 而非 [2,3]；若两棵树都写反倒也能对上，但只要有一处顺序不一致就会误判。

错误写法：叶子判定写成 root.left == null || root.right == null → 用例某节点只有左孩子时会被当成叶子，把这个内部节点的值错误地写进序列，同时整棵左子树的真实叶子被跳过。

错误写法：递归入口不判空，直接 dfs(root.left, nums) → 用例 [1,2]（根只有左孩子），进入 dfs(null) 后第一行访问 null.left 抛空指针异常。

错误写法：不做叶子判定，对每个访问到的节点都执行 nums.add(root.val) → 用例 [1,2,3]，序列变成 [1,2,3] 而不是 [2,3]，内部节点污染了特征值，与任何另一棵树比较都会得到错误结论。

错误写法：比较时只检查长度或只检查前 min(len1, len2) 位 → 用例 root1 叶值 [6,7]、root2 叶值 [6,7,4]，只比前两位会返回 true，期望 false。

错误写法：Go 里直接用 l1 == l2 比较切片 → 切片不支持 == 运算，编译报错；必须逐位比较或先比长度。

错误写法：Java 里用 l1 == l2 比较列表引用 → 两个不同的 ArrayList 对象引用恒不相等，任何输入都返回 false；必须用 equals。

错误写法：认为节点值为 0 的叶子可以跳过（当作空） → 用例某棵树的叶值序列含 0，跳过后序列长度变短，与另一棵树比较时误判为不同。

相似题目

题目	难度	考察点
100. 相同的树	简单	形状必须完全一致，可以两棵树同步递归比较，无需先降维成序列
144. 二叉树的前序遍历	简单	收集的是全部节点而非仅叶子，进阶要求用显式栈或 Morris 遍历替代递归
257. 二叉树的所有路径	简单	到达叶子时要输出整条根到叶的路径，需要在递归中维护并回溯路径栈
543. 二叉树的直径	简单	递归返回值（子树深度）与全局答案（最长路径）承担不同职责，是典型的双轨递归