LeetCode 100. 相同的树

约 3 分钟
文章信息 13 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 面试经典 150 题 腾讯 字节 阿里 京东 百度 快手 滴滴
标签
深度优先搜索 树 广度优先搜索 二叉树

题目描述

✅ 100. 相同的树

image-20260928220107864

image-20260928220107865

image-20260928220107866

题意分析

两棵树相同，要求对应位置的节点要么都不存在，要么都存在且值相等。左右孩子的位置也属于结构，因此不能只比较节点值的集合或忽略空位的遍历序列。

解法：递归同步比较

核心思路

[!blue]

一棵非空树由根节点、左子树和右子树组成。把 isSameTree(p, q) 定义为“以 p、q 为根的两棵子树是否相同”，就能把整棵树的判断拆成根值相等、左子树相同、右子树相同三个条件。

递归一直沿相同方向向下比较，两个参数始终代表对应位置。遇到空节点时，双方都空表示这一位置匹配，只有一方为空表示结构不同。这个边界判断覆盖叶子之后的位置；逐层返回时，只要根和两对子树都匹配，整棵子树就必然匹配。

解题步骤

  • 若至少一个节点为空，直接返回 p == q：同时为空为真，只有一个为空为假。
  • 两个节点都非空时，依次比较根值、p.left 与 q.left、p.right 与 q.right。
  • 用 && 连接这三个条件。某个条件为假时，后面的比较无需继续；全部为真才返回 true。
  • 每次递归都进入更小的子树，最终会到达空节点。两棵空树也会直接返回 true。

代码实现

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 同时为空才结构匹配，只有一侧为空则失败。
        if (p == null || q == null) {
            return p == q;
        }

        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    // 同时为空才结构匹配，只有一侧为空则失败。
    if p == nil || q == nil {
        return p == q
    }
    return p.Val == q.Val &&
        isSameTree(p.Left, q.Left) &&
        isSameTree(p.Right, q.Right)
}

复杂度分析

  • 时间复杂度：$O(\min(m,n)+1)$，其中 $m$、$n$ 是两棵树的节点数；每对对应节点最多比较一次，遇到差异会提前结束。两棵树完全相同时可写为 $O(n)$。
  • 空间复杂度：$O(h+1)$，其中 $h$ 是共同遍历到的非空节点的最大深度，来自递归调用栈。树退化为链时，最坏为 $O(\min(m,n)+1)$；两棵空树只占常数空间。

关键点总结

[!green]

  • 递归参数既记录当前子树，也保证两边处于同一个位置，无需额外保存路径。
  • 空节点负责比较结构，非空节点负责比较值；两者缺一不可。
  • 相同要求三个条件同时成立，发现任一差异即可结束。

易错点总结

[!yellow]

  • 在判空前访问 val 会产生空指针异常。
  • 写成 if (p == null || q == null) return false 会把两棵空树误判为不同，应返回 p == q。
  • 递归时交叉比较左右孩子判断的是镜像关系，不是相同关系。

相似题目

题目 难度 关联与区别
101. 对称二叉树 简单 比较节点值相同，但原题交叉比较左右子树以验证镜像，本题按同一方向比较。
572. 另一棵树的子树 简单 本题判断两个根对应的树完全相同，是子树搜索中验证候选根的基础。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/95440840
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！