LeetCode 572. 另一棵树的子树

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 572. 另一棵树的子树

思路分析

思路描述

参考代码

func isSubtree(s *TreeNode, t *TreeNode) bool {
	if s == nil {
		return false
	}

	if isSameTree(s, t) {
		return true
	}

	return isSubtree(s.Left, t) || isSubtree(s.Right, t)
}

func isSameTree(s *TreeNode, t *TreeNode) bool {
	if s == nil && t == nil {
		return true
	}
	if s == nil || t == nil {
		return false
	}

	return s.Val == t.Val && isSameTree(s.Left, t.Left) && isSameTree(s.Right, t.Right)
}

// 判断两棵树是否相同
func isSameTree(t1, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return t1.Val == t2.Val && isSameTree(t1.Left, t2.Left) && isSameTree(t1.Right, t2.Right)
}

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

时间复杂度：O (n * m)，其中 n 是 root 的节点数，m 是 subRoot 的节点数。

最坏情况下，我们需要遍历 root 的每个节点，并在每个节点处比较 subRoot。

空间复杂度：O (h)，其中 h 是树的高度，主要用于递归调用栈的空间。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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