Intuition
Do a Binary Tree Preorder Traversal until you reach a start point which matches the subRoot. Once there, check if each node matches, recursively.
Complexity
Runtime
- , where N is the number of nodes.
Space
Code
Simplified
# Definition for a binary tree node.
# 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:
def is_matching(node1, node2):
if node1 is None and node2 is None:
return True
if node1 is None or node2 is None:
return False
return node1.val == node2.val and \
is_matching(node1.left, node2.left) \
and is_matching(node1.right, node2.right)
def r(node):
if not node:
return False
return is_matching(node, subRoot) or r(node.left) or r(node.right)
return r(root)Verbose
# Definition for a binary tree node.
# 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:
def is_matching(node1, node2):
if node1 is None and node2 is None:
return True
if node1 is None or node2 is None:
return False
return node1.val == node2.val and \
is_matching(node1.left, node2.left) \
and is_matching(node1.right, node2.right)
def r(node):
if not node:
return False
if node.val == subRoot.val:
if is_matching(node, subRoot):
return True
if r(node.left):
return True
if r(node.right):
return True
return False
return r(root)Notes
Cards
START Basic Front: Subtree Of Another Tree Back: For each node, check both left and right subtrees for a match. END