#572. 另一棵树的子树

LeetCode 原题链接

#题目描述

给定二叉树 root 和 subRoot，判断 root 中是否存在一棵与 subRoot 结构和值完全相同的子树。

这里的“子树”不是任意截取一段结构，而是必须以 root 中某个节点为根，并包含这个节点下面的所有后代。

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

#题型判断

问题分为两层：

1. 在 root 中枚举可能的子树根节点。
2. 判断从两个根节点开始的树是否完全相同。

两层都天然适合递归 DFS。只找到相同根值不够，还必须比较完整结构。

#核心思路

• isSameTree(first, second) 同步比较两棵树。
• isSubtree(root, subRoot) 判断当前位置是否相同；若不同，再去左右子树寻找。

isSameTree(first, second) 判断两棵树是否完全相同：

1. 两个节点都为空，说明这一侧都没有节点，返回 true。
2. 只有一个节点为空，说明结构不同，返回 false。
3. 两个节点值不同，返回 false。
4. 当前节点相同后，继续比较左子树和右子树。

isSubtree(root, subRoot) 负责枚举 root 中的每个节点：

1. 先判断以当前 root 为根的树，是否和 subRoot 完全相同。
2. 如果不同，再去 root.left 中继续找。
3. 如果左子树也没有，再去 root.right 中继续找。

#执行过程示例

以 root = [3,4,5,1,2]、subRoot = [4,1,2] 为例：

先从 root = 3 开始比较
3 !== 4，不匹配

继续去左子树 root = 4 比较
4、1、2 的结构和值都和 subRoot 相同

所以返回 true

#代码实现

var isSubtree = function (root, subRoot) {
  const isSameTree = (first, second) => {
    if (!first && !second) return true;
    if (!first || !second) return false;
    if (first.val !== second.val) return false;

    return (
      isSameTree(first.left, second.left) &&
      isSameTree(first.right, second.right)
    );
  };

  if (!root) return false;

  return (
    isSameTree(root, subRoot) ||
    isSubtree(root.left, subRoot) ||
    isSubtree(root.right, subRoot)
  );
};

#复杂度分析

设 root 有 n 个节点，subRoot 有 m 个节点：

• 时间复杂度：最坏 O(n × m)，每个候选节点都可能比较 m 个节点。
• 空间复杂度：O(h1 + h2)，来自枚举和比较时的递归栈。最坏情况下两棵树都退化成链表，空间复杂度为 O(n + m)；平衡二叉树中约为 O(log n + log m)。

#边界与易错点

• LeetCode 约束中 subRoot 非空；若业务定义允许空树，通常应约定空树是任意树的子树。
• 当 root 为空而 subRoot 非空时，返回 false。
• 子树必须从某个节点开始，并包含这个节点的所有后代，不能只匹配中间一部分结构。
• 不能只比较先序遍历的节点值，必须保留空节点标记才能区分结构。
• 数据量更大时，可以序列化后做字符串匹配，或使用树哈希降低重复比较成本。