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) {
  // 判断以 first 和 second 为根的两棵树是否结构相同且节点值相等
  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)
    );
  };

  // 已经越过 root 的叶节点，仍未找到匹配的子树
  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。
  • 子树必须从某个节点开始，并包含这个节点的所有后代，不能只匹配中间一部分结构。
  • 不能只比较先序遍历的节点值，必须保留空节点标记才能区分结构。
  • 数据量更大时，可以序列化后做字符串匹配，或使用树哈希降低重复比较成本。