树与图简单1 种解法
#572另一棵树的子树
判断 subRoot 是否与 root 的某个节点为根的整棵子树完全相同。
#二叉树#深度优先搜索
原题
给你两棵二叉树 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
提示：
root树上的节点数量范围是[1, 2000]subRoot树上的节点数量范围是[1, 1000]-104 <= root.val <= 104-104 <= subRoot.val <= 104
解题主线
- 在 root 的每个候选节点上调用“相同的树”比较。
解法 1：枚举根并比较
当前节点匹配失败后，递归尝试左右子树作为候选根。
-
时间复杂度： O(nm) 最坏，n、m 分别为两棵树节点数
-
空间复杂度： O(h1 + h2) 最坏
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// 外层递归枚举 root 的每个节点作为候选子树根。
// 候选命中要求值与左右结构同时完全一致，而非只匹配节点序列。
// 空目标树视为任意树的子树；非空目标无法匹配空主树。
if (subRoot == null) return true;
if (root == null) return false;
return same(root, subRoot)
|| isSubtree(root.left, subRoot)
|| isSubtree(root.right, subRoot);
}
private boolean same(TreeNode first, TreeNode second) {
if (first == null || second == null) return first == second;
return first.val == second.val
&& same(first.left, second.left)
&& same(first.right, second.right);
}
}边界与易错点
- 匹配要求结构和值都相同，不是只包含目标节点序列。
- 约定空树是任意树的子树可让辅助方法语义完整。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q572_isSubTree.java