LeetCode 872. 叶子相似的树

约 5 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 简单 LeetCode 75
标签
深度优先搜索 树 二叉树

题目描述

✅ 872. 叶子相似的树

image-20260928233847865

image-20260928233847867

image-20260928233847869

题意分析

把一棵树的所有叶子按从左到右的顺序取出它们的值，得到叶值序列。判断两棵树的这个序列是否完全相同：长度、每个位置的值以及重复次数都必须一致。

只比较叶子，内部节点的值和树的整体形状不需要相同。叶子必须同时没有左右孩子，只有一侧为空的节点仍是内部节点。题目保证两棵树都非空。

解法：按从左到右顺序收集叶值

核心思路

[!blue]

分别遍历两棵树，只在叶子处记录值。要得到从左到右的顺序，每个节点都先完整遍历左子树，再完整遍历右子树：左子树中的所有叶子都位于右子树叶子的左边，递归内部继续遵守相同规则，就能得到全树的叶值顺序。

如果当前节点是叶子，将它的值追加到列表后返回；否则只递归存在的孩子。内部节点不写入列表，所以即使两棵树的根值、层数或分叉形状不同，也不会干扰真正要比较的序列。

代码用左右孩子引用是否相同判断叶子。正规二叉树不会让两个孩子共享同一个非空节点，因此引用相同只可能是两边都为空；这个比较并不是比较左右孩子的数值。根由题目保证非空，递归调用前又检查孩子存在，所以函数内部无需再处理空参数。

收集完成后比较两个序列。Java 的 List.equals 同时检查长度及对应值，Go 则先检查长度，再逐位置比较。长度不同或者任一位置不同，就不满足叶相似；只有完整一致才返回真。

每个节点都只访问一次，比较的是有顺序的列表而非集合，因而不会丢掉同值叶子多次出现的信息。

解题步骤

  1. 为两棵树分别创建叶值列表。
  2. 从根开始 DFS，遇到叶子就追加当前值并返回。
  3. 非叶子先处理非空左孩子，再处理非空右孩子。
  4. 比较两个叶值列表是否长度相同且逐项相同，返回结果。

代码实现

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(L + \max(h_1, h_2))$，L 为两树叶子总数，h_1、h_2 为树高。两个结果列表需要同时保留，两次递归则先后执行，只计较大的栈深度。

关键点总结

[!green]

  • 先左后右保证叶值的空间顺序，只有真正的叶子进入结果。
  • 树的内部结构可以不同，比较单位是叶值序列。
  • 列表保留顺序与次数，才能表达叶相似的完整条件。

易错点总结

[!yellow]

  • 只比较叶子集合、数量或总和，会漏掉顺序与重复次数上的差异。
  • 只有一侧孩子为空就判为叶子，会把内部节点值误加入序列。
  • 改为先右后左遍历其中一棵树，会让两份列表采用不同顺序。
  • 将 left == right 误读为孩子值相等，可能把两个同值非空孩子的父节点当成叶子。
  • 比较整棵树的形状或全部节点值，会把本来叶相似的不同结构错误排除。

相似题目

题目 难度 关联与区别
100. 相同的树 简单 原题要求所有节点及结构相同，本题只比较从左到右的叶值序列。
94. 二叉树的中序遍历 简单 都依靠先处理左侧来稳定输出顺序，本题只输出叶子而不是所有中序节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/70402381
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！