LeetCode 572. 另一棵树的子树

2026-04-14 HGNULB 约 5 分钟

文章信息 16 个分类 · 5 个标签

分类

LeetCode CodeTop 简单 未解决 20-50 腾讯 字节 阿里 华为 微软 百度 网易 快手 滴滴 商汤 猿辅导

标签

深度优先搜索 树 二叉树 哈希函数 字符串匹配

题目描述

✅ 572. 另一棵树的子树

题意分析

判断目标树 subRoot 是否与原树 root 中某个节点开始的整棵子树完全相同。候选子树必须包含该节点的所有后代，节点值、左右位置和缺失孩子的情况都要一致。

原树自身也可以作为候选子树。只找到若干相同的值、或只匹配目标的一部分结构都不够；原树候选位置多出的后代也会使匹配失败。

解法：枚举起点并比较整棵子树

核心思路

[!blue]

将任务分为两个独立问题：先找一个可能的子树根，再检查从这个根开始是否与完整目标相同。外层 isSubtree 负责枚举起点，内层 same 负责逐节点验证，两者的判断方式不同。

外层先尝试当前节点。如果当前候选不能匹配，目标仍可能出现在左子树或右子树，所以继续递归原树两侧，并用逻辑或连接三个结果。每次只移动原树的候选位置，subRoot 始终保持不变，确保寻找的是同一棵完整目标树。

内层比较两个对应节点：同时为空说明这一处结构恰好结束，返回真；只有一边为空说明结构不同，或两边值不同，返回假。当前值相同后，必须要求左对左、右对右都相同，因此用逻辑与合并两个子结果。

外层能走到原树中的每个节点，不会漏掉任何候选根；内层同时验证数值和空节点位置，只有完整结构一致才成功。只要任一候选成功即可停止，否则遍历完仍未匹配就返回失败。

解题步骤

1. 外层当前原树节点为空时，返回目标是否也为空。
2. 调用 same(root, subRoot)，把当前节点作为根进行完整匹配。
3. 若不匹配，继续检查 root.left 和 root.right，两次递归都使用原来的 subRoot。
4. 内层先处理两节点为空的情况：同时为空成功，只有一边为空失败。
5. 两节点都存在时，先比较值，再要求左右两侧分别完整匹配。
6. 外层任一位置成功即返回 true，所有候选失败才返回 false。

代码实现

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return subRoot == null;
        }

        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 true;
        }

        if (first == null || second == null || first.val != second.val) {
            return false;
        }

        // 子树匹配要求左右结构和值都完全一致。
        return same(first.left, second.left) && same(first.right, second.right);
    }
}

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return subRoot == nil
    }
    return sameTree(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

func sameTree(first *TreeNode, second *TreeNode) bool {
    if first == nil && second == nil {
        return true
    }
    if first == nil || second == nil || first.Val != second.Val {
        return false
    }

    // 必须从当前节点开始整棵树完全一致。
    return sameTree(first.Left, second.Left) && sameTree(first.Right, second.Right)
}

复杂度分析

• 时间复杂度：最坏 $O(mn)$。外层最多枚举 m 个候选，每次内层最多比较 n 个节点。
• 空间复杂度：$O(h_1 + h_2)$，h_1、h_2 分别为原树和目标树高度；这是两层递归的空间上界，退化树下不超过 $O(m+n)$。

关键点总结

[!green]

• 找位置与比整树是两种递归：外层改变候选根，内层同步推进两棵树。
• 外层用“或”表达存在一个成功起点，内层用“与”表达所有对应位置都匹配。
• 空孩子也属于结构信息，只有两边同时结束才能认为该分支相同。

易错点总结

[!yellow]

• 内层只要目标节点为空就返回成功，会允许原树继续长出额外后代，把子树判断变成较宽松的子结构匹配。
• 两边同时为空也判失败，会让任何完整匹配都无法在叶子处结束。
• 外层寻找候选时同步移动目标，会把目标越找越短，不再验证原来的整棵树。
• 只比较根值就返回，无法识别重复值、左右位置不同或缺失孩子等结构差异。
• 内层把左右匹配用“或”连接，会只匹配一侧就放行，丢掉另一侧的完整性要求。

相似题目

题目	难度	关联与区别
100. 相同的树	简单	从大树的每个候选根出发，完整匹配两棵树时复用相同树判断。
剑指 Offer 26. 树的子结构	中等	子结构允许大树在模式结束处继续延伸，本题要求整棵子树的结构也完全相同。
101. 对称二叉树	简单	递归比较对应节点及两侧子树；本题在大树各位置寻找相同子树，该题比较左右镜像位置。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/87495972

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！