LeetCode 572简单树
另一棵树的子树 图解题解
光找到值相等的节点还不够——结构也得一模一样。
在一本书里找一段文字，光找「第一句话出现在哪」不够——还得逐字核对后续每一行才算真正命中。算法也一样：在大树每个节点处发起一次「整棵结构比对」，值相同就递归验左子树、再验右子树，左右都完全吻合才算找到，有一处不同立刻判否。
这道题到底在问什么
判断 subRoot 是否是 root 的一棵完整子树。
- 示例
- root=[3,4,5,1,2], subRoot=[4,1,2] → true
最优解：一步一步想明白
- 3只看值是否出现会误判，必须比较整棵结构。
- 4在 root 每个节点处尝试 sameTree：值相同、左右子树也相同才算命中。
- 5在 root 里找一棵和 subRoot 完全相同的子树。逐个节点当候选根。先以 3 试：3 ≠ subRoot 的根 4 → 不匹配，继续递归。
- 6递归到节点 4：它的值和 subRoot 的根 4 相等 → 值得把整棵子树比一比。
- 7关键帧：把以 4 为根的子树 [4,1,2] 和 subRoot [4,1,2] 逐节点比：根、左、右全相等 → 子树命中！
- 8找到一棵和 subRoot 完全相同的子树 → 返回 true。
- 9关键：必须整棵子树完全相同(每个节点值 + 结构都一致)。若 subRoot 少了那个 2，就不算 4 的子树 —— 子树是「连根带所有后代」，不能多也不能少。
- 12一句话记住：在 root 每个节点处尝试 sameTree：值相同、左右子树也相同才算命中。
- 21这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=tree 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：只比根节点值相等就算命中
✓ 对：必须整棵子树逐节点都相同
子树要连根带所有后代完全一致，只匹配根会误判。
✗ 错：漏判 subRoot/root 为空
✓ 对：subRoot 空→true、root 空→false
空 subRoot 是任意树的子树；root 空则无处可匹配。
✗ 错：sameTree 里没先判空就比值
✓ 对：先处理两节点空/非空组合
空节点没有 val，直接比会空指针。
完整代码（Python / C++ / Java）
Python
class Solution:
def isSubtree(self, root, subRoot):
def same(a, b):
if not a and not b:
return True
if not a or not b or a.val != b.val:
return False
return same(a.left, b.left) and same(a.right, b.right)
if not subRoot:
return True
if not root:
return False
return same(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)C++
class Solution {
public:
bool same(TreeNode* a, TreeNode* b) {
if (!a && !b) return true;
if (!a || !b || a->val != b->val) return false;
return same(a->left, b->left) && same(a->right, b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!subRoot) return true;
if (!root) return false;
return same(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};Java
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
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 a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null || a.val != b.val) return false;
return same(a.left, b.left) && same(a.right, b.right);
}
}套路模板 · 遍历 + 同构判断
# 子树判断骨架
def isSubtree(root, subRoot):
if not subRoot: return True
if not root: return False
if same(root, subRoot): return True # 当前节点为根试一试
return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)
# same(a,b): 判两棵树是否逐节点完全相同(同 LC100)复杂度
时间复杂度
O(m·n)
m 个 root 节点，每个最坏触发一次 O(n) 的同构比较
空间复杂度
O(h)
递归栈深度 = 树高
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 另一棵树的子树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
遍历 root 的每个节点，以它为根调用 sameTree(node, subRoot)；任一处「完全相同」即返回 true。sameTree 是判两树是否逐节点一致的子过程。
这道题为什么用「树」，换最直接的暴力解会差在哪？+
树抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。