LeetCode 572. 另一棵树的子树

Categories:

Tags:

题目描述
思路分析
1. 解法一：DFS 递归（推荐）
2. 解法二：序列化 + KMP 字符串匹配
相似题目

题目描述

✅ 572. 另一棵树的子树

思路分析

解法一：DFS 递归（推荐）

核心思路：

对 root 的每个节点，判断以该节点为根的子树是否与 subRoot 完全相同

先写辅助函数 isSameTree 判断两棵树是否完全一致（值、结构均相同）

在 isSubtree 中，对当前节点调用 isSameTree，若相同则返回 true；否则递归检查左、右子树

终止条件：root == nil 时返回 false（空树不包含任何非空子树）

复杂度分析：

时间复杂度：O(n × m)，其中 n 是 root 的节点数，m 是 subRoot 的节点数，最坏情况下每个节点都要做一次完整比较

空间复杂度：O(n)，递归栈深度取决于 root 的高度，最坏为 O(n)

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        // 当前节点与 subRoot 完全相同，直接返回 true
        if (isSameTree(root, subRoot)) {
            return true;
        }
        // 递归检查左子树和右子树
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        // 两者均为空，视为相同
        if (p == null && q == null) {
            return true;
        }
        // 一方为空，另一方非空，不相同
        if (p == null || q == null) {
            return false;
        }
        // 值不同，不相同
        if (p.val != q.val) {
            return false;
        }
        // 递归比较左右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

// isSameTree 判断两棵树是否完全相同
func isSameTree(p, q *TreeNode) bool {
    // 两者均为空，视为相同
    if p == nil && q == nil {
        return true
    }
    // 一方为空，另一方非空，不相同
    if p == nil || q == nil {
        return false
    }
    // 值不同，不相同
    if p.Val != q.Val {
        return false
    }
    // 递归比较左右子树
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

// isSubtree 判断 subRoot 是否是 root 的子树
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return false
    }
    // 当前节点与 subRoot 完全相同，直接返回 true
    if isSameTree(root, subRoot) {
        return true
    }
    // 递归检查左子树和右子树
    return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

解法二：序列化 + KMP 字符串匹配

核心思路：

将 root 和 subRoot 分别序列化为字符串（前序遍历，空节点用特殊占位符表示）

判断 subRoot 的序列化串是否是 root 序列化串的子串，转化为经典的字符串匹配问题

使用 KMP 算法在 O(n + m) 时间内完成匹配，避免暴力匹配的 O(n × m) 开销

序列化时须在每个节点值前后加分隔符（如 #1,），防止 12 被误匹配为含 1 和 2 的子树

复杂度分析：

时间复杂度：O(n + m)，其中 n、m 分别为两棵树的节点数，序列化各为 O(n)、O(m)，KMP 匹配为 O(n + m)

空间复杂度：O(n + m)，存储两棵树的序列化字符串及 KMP 失配数组

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String s = serialize(root);
        String t = serialize(subRoot);
        // 利用 KMP 判断 t 是否是 s 的子串
        return kmpContains(s, t);
    }

    // 前序序列化，用 "#值," 格式避免歧义
    private String serialize(TreeNode node) {
        if (node == null) {
            return "#null,";
        }
        return "#" + node.val + "," + serialize(node.left) + serialize(node.right);
    }

    // KMP 字符串匹配，判断 pattern 是否是 text 的子串
    private boolean kmpContains(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        if (m == 0) {
            return true;
        }
        // 构建 KMP 失配数组
        int[] fail = new int[m];
        fail[0] = 0;
        for (int i = 1; i < m; i++) {
            int j = fail[i - 1];
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = fail[j - 1];
            }
            fail[i] = pattern.charAt(i) == pattern.charAt(j) ? j + 1 : 0;
        }
        // KMP 匹配
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = fail[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                return true;
            }
        }
        return false;
    }
}

// serialize 将二叉树前序序列化为字符串，用 "#值," 格式避免歧义
func serialize(node *TreeNode) string {
    if node == nil {
        return "#null,"
    }
    return fmt.Sprintf("#%d,", node.Val) + serialize(node.Left) + serialize(node.Right)
}

// buildFail 构建 KMP 失配数组
func buildFail(pattern string) []int {
    m := len(pattern)
    fail := make([]int, m)
    for i := 1; i < m; i++ {
        j := fail[i-1]
        for j > 0 && pattern[i] != pattern[j] {
            j = fail[j-1]
        }
        if pattern[i] == pattern[j] {
            fail[i] = j + 1
        }
    }
    return fail
}

// isSubtree 将子树问题转化为字符串匹配，用 KMP 求解
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    text := serialize(root)
    pattern := serialize(subRoot)
    fail := buildFail(pattern)
    m := len(pattern)
    // KMP 匹配
    j := 0
    for i := 0; i < len(text); i++ {
        for j > 0 && text[i] != pattern[j] {
            j = fail[j-1]
        }
        if text[i] == pattern[j] {
            j++
        }
        if j == m {
            return true
        }
    }
    return false
}

相似题目

题目	难度	考察点
100. 相同的树	简单	递归 / DFS / 树结构比较
101. 对称二叉树	简单	递归 / DFS / 镜像比较
226. 翻转二叉树	简单	递归 / DFS
110. 平衡二叉树	简单	递归 / 后序遍历
543. 二叉树的直径	简单	递归 / 后序遍历
951. 翻转等价二叉树	中等	递归 / 树结构比较
1367. 二叉树中的链表	中等	递归 / DFS / 子结构匹配

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/87495972