572. Subtree of Another Tree

Problem Statement

link: LeetCode.cn LeetCode Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

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

Example:

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

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

Constraints:

The number of nodes in the root tree is in the range [1, 2000]. The number of nodes in the subRoot tree is in the range [1, 1000]. -104 <= root.val <= 104 -104 <= subRoot.val <= 104

Solution Approach

The solution recursively checks if the subtree rooted at any node in the main tree is identical to the given subRoot tree by comparing node values and their respective left and right subtrees.

Algorithm

1. Subtree Matching: Traverse the main tree and at each node, check if the subtree rooted at that node is identical to the subRoot tree.
2. Tree Comparison: Use a helper function to compare two trees by checking if the current nodes and their respective left and right subtrees match.
3. Recursive Check: Recursively apply the comparison at each node of the main tree, returning true if a match is found, or false otherwise.

Implement

    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: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root and not subRoot:
            return True
        if not root or not subRoot:
            return False
        return self.isSame(root, subRoot) or\
            self.isSubtree(root.left, subRoot) or\
            self.isSubtree(root.right, subRoot)
    def isSame(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return s.val == t.val and self.isSame(s.left, t.left) and\
            self.isSame(s.right, t.right)
        

    
    

Twitter  facebook  Email