LeetCode: 572 Subtree of Another Tree

Given the roots of two binary trees root and subRoot, write a function to determine if subRoot is a subtree of root.

A subtree of a binary tree T is a tree that consists of a node in T and all of this node’s descendants. The tree T could also be considered a subtree of itself.

Example:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

问题

给定两个二叉树的根节点 root 和 subRoot，编写一个函数来判断 subRoot 是否是 root 的子树。

二叉树 T 的子树是指 T 中的一个节点及其所有后代构成的树。树 T 也可以被视为它自己的子树。

解决方案 1

递归法

Approach 1 / 方法 1

This solution uses recursion to check if subRoot is a subtree of root. The idea is to traverse the root tree and at each node, check if the tree rooted at that node is identical to subRoot. If any such subtree is found, we return True.

该解决方案使用递归方法来检查 subRoot 是否是 root 的子树。其思想是遍历 root 树，并在每个节点处检查以该节点为根的树是否与 subRoot 相同。如果找到任何这样的子树，我们返回 True。

Implementation / 实现

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False
        if self.isSameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and not t:
            return True
        if not s or not t:
            return False
        if s.val != t.val:
            return False
        return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)

Explanation / 解释

Check if root is None / 检查 root 是否为 None
```
if not root:
   return False
```
- English: If the root is None, there can’t be a subtree, so we return False.
- Chinese: 如果 root 为 None，则不可能有子树，因此我们返回 False。
Check if the Current Tree is the Same as subRoot / 检查当前树是否与 subRoot 相同
```
if self.isSameTree(root, subRoot):
   return True
```
- English: We use the isSameTree helper function to check if the tree rooted at the current node is identical to subRoot. If it is, we return True.
- Chinese: 我们使用 isSameTree 辅助函数来检查以当前节点为根的树是否与 subRoot 相同。如果相同，我们返回 True。
Recursively Check Left and Right Subtrees / 递归检查左右子树
```
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
```
- English: If the current tree is not identical to subRoot, we recursively check the left and right subtrees of root to see if either contains subRoot as a subtree.
- Chinese: 如果当前树与 subRoot 不同，我们递归检查 root 的左子树和右子树，看它们是否包含 subRoot 作为子树。
Helper Function isSameTree / 辅助函数 isSameTree
- English: This function is used to determine if two trees are identical. It checks if both nodes are None, if one is None but not the other, or if their values are different. If the values match, it recursively checks the left and right children.
- Chinese: 该函数用于确定两棵树是否相同。它检查两个节点是否都为 None，如果其中一个为 None 而另一个不为 None，或它们的值是否不同。如果值匹配，它递归检查左子节点和右子节点。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n * m), where n is the number of nodes in the root and m is the number of nodes in subRoot. In the worst case, we compare subRoot with every subtree of root.
Space Complexity / 空间复杂度: O(h), where h is the height of the root tree. This space is used by the recursion stack.

Key Concept / 关键概念

Recursive Tree Comparison / 递归树比较: The recursive approach efficiently checks if one tree is a subtree of another by comparing each node and its subtrees.
递归树比较: 递归方法通过比较每个节点及其子树，高效地检查一棵树是否是另一棵树的子树。

解决方案 2

序列化法

Approach 2 / 方法 2

This solution involves serializing both the root and subRoot trees into strings and then checking if the serialized string of subRoot is a substring of the serialized string of root. This approach leverages the fact that identical trees will have identical serialized strings.

该解决方案涉及将 root 和 subRoot 树序列化为字符串，然后检查 subRoot 的序列化字符串是否是 root 序列化字符串的子串。此方法利用了相同的树将具有相同的序列化字符串这一事实。

Implementation / 实现

python

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def serialize(node):
            if not node:
                return "#"
            return f",{node.val}" + serialize(node.left) + serialize(node.right)

        root_serialized = serialize(root)
        subRoot_serialized = serialize(subRoot)

        return subRoot_serialized in root_serialized

Explanation / 解释

Serialization Function / 序列化函数
```
def serialize(node):
   if not node:
       return "#"
   return f",{node.val}" + serialize(node.left) + serialize(node.right)
```
- English: The serialize function converts a tree into a string. If the node is None, it returns #. Otherwise, it returns the value of the node followed by the serialized left and right children.
- Chinese: serialize 函数将树转换为字符串。如果节点为 None，它返回 #。否则，它返回节点的值，后跟左子节点和右子节点的序列化结果。
Serialize Both root and subRoot / 序列化 root 和 subRoot
```
root_serialized = serialize(root)
subRoot_serialized = serialize(subRoot)
```
- English: We serialize both the root and subRoot trees into strings.
- Chinese: 我们将 root 和 subRoot 树序列化为字符串。
Check if subRoot is a Substring of root / 检查 subRoot 是否是 root 的子串
```
return subRoot_serialized in root_serialized
```
- English: We check if the serialized string of subRoot is a substring of the serialized string of root. If it is, then subRoot is a subtree of root, so we return True.
- Chinese: 我们检查 subRoot 的序列化字符串是否是 root 序列化字符串的子串。如果是，则 subRoot 是 root 的子树，因此我们返回 True。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n + m), where n is the number of nodes in root and m is the number of nodes in subRoot. The serialization process takes O(n) time for `

root and O(m) time for subRoot`.

Space Complexity / 空间复杂度: O(n + m), where n is the size of the serialized root and m is the size of the serialized subRoot.

Key Concept / 关键概念

Tree Serialization / 树的序列化: By converting trees into strings, we can leverage string operations to check for subtree relationships efficiently.
树的序列化: 通过将树转换为字符串，我们可以利用字符串操作来高效地检查子树关系。

Comparison / 比较

Efficiency / 效率:
- Recursive Approach / 递归方法: More intuitive and direct but may be less efficient for large trees.
- Serialization Approach / 序列化方法: More efficient for certain cases, especially when leveraging string matching algorithms.
Use Case / 使用场景:
- Recursive / 递归: Preferred when working with smaller trees or when a clear and direct comparison is needed.
- Serialization / 序列化: Useful when handling large trees where serialization and string matching can speed up the process.

Summary / 总结

English: Both the recursive and serialization approaches are valid for determining if one tree is a subtree of another. The recursive method is more straightforward, while the serialization method can be more efficient in certain cases.
Chinese: 递归和序列化方法都可以有效地确定一棵树是否是另一棵树的子树。递归方法更直接，而序列化方法在某些情况下可能更高效。

Tips / 提示

English: Use the recursive approach for smaller or simpler trees and the serialization approach for larger trees or when performance is critical.
Chinese: 对于较小或较简单的树，使用递归方法；对于较大的树或性能至关重要时，使用序列化方法。

Solution Template for Similar Questions / 提示

English: For problems involving tree comparison, consider both recursive and serialization approaches depending on the problem’s constraints and requirements.
Chinese: 对于涉及树比较的问题，根据问题的限制和要求，考虑递归和序列化方法。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice identifying subtrees using both recursive and serialization methods to understand the strengths and limitations of each approach.
Chinese: 通过递归和序列化方法练习识别子树，以了解每种方法的优缺点。

Subtree of Another Tree – Leetcode 572 – Python by NeetCode

Post Views: 330

CODEBITWAVE

LeetCode: 572 Subtree of Another Tree

问题

解决方案 1

Approach 1 / 方法 1

Implementation / 实现

python

Explanation / 解释

Complexity Analysis / 复杂度分析

Key Concept / 关键概念

解决方案 2

Approach 2 / 方法 2

Implementation / 实现

python

Explanation / 解释

Complexity Analysis / 复杂度分析

Key Concept / 关键概念

Comparison / 比较

Summary / 总结

Tips / 提示

Solution Template for Similar Questions / 提示

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

Comments

Leave a Reply Cancel reply