0572.另一棵树的子树

难度：🟢 简单

标签：树、深度优先搜索、二叉树、递归

链接：572. 另一棵树的子树

题目描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含一个与 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

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

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

解题思路

核心思想

本题的核心问题可以分解为两个子问题：

1. 如何判断两棵树是否完全相同？

2. 如何遍历 root 树中的每一个节点，并以该节点为根的子树与 subRoot 进行比较？

这自然地导向了一个递归的解决方案。

思路选择

深度优先搜索 (DFS) 是解决此问题的标准方法。我们可以定义两个递归函数：

• 主函数 isSubtree(root, subRoot)：它的任务是遍历 root 树。对于 root 树中的每一个节点，它都会去判断以此节点为根的子树是否和 subRoot 完全相同。这个判断可以描述为： isEqualTree(root, subRoot) OR isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot)。

• 辅助函数 isEqualTree(node1, node2)：它的任务是判断两棵树是否在结构和节点值上完全相同。

关键步骤

1. 定义主函数 isSubtree: a. 终止条件: 如果 root 为 null，那么 subRoot 不可能存在于其中（除非 subRoot 也为 null，但通常 subRoot 是非空的），返回 false。 b. 递归逻辑: 判断以下三种情况是否有一种为真： i. 当前 root 和 subRoot 就是相同的树。 ii. subRoot 是 root.left 的子树。 iii. subRoot 是 root.right 的子树。

2. 定义辅助函数 isEqualTree: a. 终止条件 1: 如果两个节点都为 null，它们是相同的，返回 true。 b. 终止条件 2: 如果只有一个节点为 null，或者它们的值不相等，则它们不同，返回 false。 c. 递归逻辑: 只有当两个节点的左子树相同 并且 右子树也相同时，这两棵树才算相同。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */

// 辅助函数：判断两棵树是否完全相同
var isEqualTree = function (node1, node2) {
    if (node1 === null && node2 === null) return true;
    if (node1 === null || node2 === null) return false;
    return node1.val === node2.val && isEqualTree(node1.left, node2.left) && isEqualTree(node1.right, node2.right);
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
var isSubtree = function (root, subRoot) {
    // 如果 root 为空，无法构成子树关系
    if (root === null) return false;

    // 判断：当前树是否与 subRoot 相同 OR subRoot 是否是左子树的子树 OR subRoot 是否是右子树的子树
    return isEqualTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

复杂度分析

• 时间复杂度：O(m × n) 其中 m 是 root 树的节点数，n 是 subRoot 树的节点数。在最坏的情况下，我们需要对 root 的每个节点都调用一次 isEqualTree，而 isEqualTree 本身需要 O(n) 的时间。

• 空间复杂度：O(m) 在最坏的情况下（树退化为链表），递归调用的栈深度可以达到 root 树的高度，即 O(m)。

相关题目

• 0100.相同的树

• 0101.对称二叉树

• 0543.二叉树的直径

总结

本题是考察二叉树递归思想的经典题目。通过将问题分解为“判断两棵树是否相同”和“遍历所有可能的子树起点”这两个子任务，可以清晰地构建出递归解法。这是检验对树的深度优先搜索和问题分解能力的好题目。