如何判断两棵树相同？如何判断一棵树是否是另一棵树的子树？

简化版

判断两棵树相同要同时比较结构和值：两个都空为 true，一个空一个非空为 false，值相等后递归比较左右子树。判断子树则是在主树每个节点尝试一次“相同树”匹配，朴素时间 O(mn)，也可用序列化或哈希优化。

详细版

相同树是基础递归题，函数语义是“以 p 和 q 为根的两棵树是否完全一致”。子树问题可以拆成两层：当前节点是否和目标树相同；如果不同，目标树是否出现在当前节点的左子树或右子树中。

boolean isSame(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val
        && isSame(a.left, b.left)
        && isSame(a.right, b.right);
}

boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    return isSame(root, subRoot)
        || isSubtree(root.left, subRoot)
        || isSubtree(root.right, subRoot);
}

子树匹配不能只比较遍历序列中的连续值，因为结构也必须一致。

完整版教学

一、相同树比较的是值和结构

两棵树“相同”有两个条件：每个对应位置的节点值相等，并且空节点位置也相同。只比较遍历结果可能误判，因为不同结构可能产生相同的值序列。递归比较天然适合这个定义，因为每个位置只需要判断当前节点和左右子树。

树 A:  1        树 B:  1
      /                \
     2                  2

如果只看非空节点前序，都是 1,2。但一个 2 是左孩子，一个 2 是右孩子，结构不同，不能算相同。

二、递归边界决定正确性

相同树有三个关键边界：两个都空返回 true，一个空一个非空返回 false，两个都非空才比较值并递归。顺序不能乱，否则会在空指针上取值。这个题的递归不是为了炫技，而是直接翻译定义。

same(a,b):
1. a == null && b == null -> true
2. a == null || b == null -> false
3. a.val == b.val && same(a.left,b.left) && same(a.right,b.right)

这套边界也是很多二叉树“镜像、对称、子结构”题的基础模板。

三、子树问题是“遍历主树 + 局部匹配”

判断 subRoot 是否是 root 的子树，不能只从根开始匹配。主树中任何一个节点都可能成为匹配起点，所以外层要遍历主树，内层要调用相同树判断。这个分层能让代码和题意对应起来。

isSubtree(root, sub):
  当前节点匹配成功 -> true
  否则去左子树找
  否则去右子树找

如果主树有 m 个节点，子树有 n 个节点，朴素情况下每个主树节点都可能触发一次 n 规模比较，最坏 O(mn)。

四、为什么序列化可以优化子树判断

如果把树序列化成带空标记的字符串，子树判断可以转成字符串包含问题。关键仍然是带空标记和分隔符，否则会出现结构或数值边界误判。例如值 12 不能和 1,2 混在一起，空孩子也必须编码。

编码方式	是否安全	原因
只拼节点值	不安全	结构丢失，数值边界混淆
前序 + 分隔符	不够安全	空孩子结构仍可能丢失
前序 + 空标记 + 分隔符	安全	值和结构都保留

序列化后可用 KMP 判断包含，复杂度可接近 O(m+n)。但在普通面试中，递归朴素版通常已经足够。

五、子树和子结构不是同一个概念

子树要求从某个节点开始，整个结构和值完全相同，包括空孩子也要一致。子结构通常只要求 B 的结构和值能在 A 中找到对应部分，B 没有的地方可以不管。不同平台对题目叫法可能不同，面试时要先确认定义。

子树:    匹配起点下面必须完全一致
子结构:  只要求目标结构覆盖的部分一致

例如目标树只有一个左孩子，主树匹配位置除了这个左孩子还有额外右孩子，是否算匹配取决于是“子树”还是“子结构”。

六、常见误区与追问

记忆钩子：相同树是“同位置同值同空位”，子树是在主树每个位置试一次相同树。

误区：遍历序列相同就表示树相同。 没有空标记的遍历序列会丢失结构。
误区：子树只要值都能匹配就行。 子树要求结构和值完整一致。
误区：主树为空时还能包含非空子树。 主树为空无法提供匹配起点。
追问：空树是不是任意树的子树？ 数学上常认为是，但很多题目会给 subRoot 非空，面试要按题目约定说明。
追问：如何优化 O(mn)？ 可用带空标记的序列化 + KMP，或树哈希减少重复比较。
追问：子树和子结构区别是什么？ 子树要求匹配起点以下完全一致，子结构只匹配目标覆盖部分。

七、加强记忆

相同树先抓“两个空、一个空、都非空”三个分支；子树再套一层“当前试、左边找、右边找”。不要被题目名字绕住，核心一直是结构和值同时匹配。若需要优化，就把结构也编码进序列化字符串，再做字符串匹配。

简化版

详细版