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.
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
Solutions
Solution 1: DFS
We define a helper function $\textit{same}(p, q)$ to determine whether the tree rooted at $p$ and the tree rooted at $q$ are identical. If the root values of the two trees are equal, and their left and right subtrees are also respectively equal, then the two trees are identical.
In the $\textit{isSubtree}(\textit{root}, \textit{subRoot})$ function, we first check if $\textit{root}$ is null. If it is, we return $\text{false}$. Otherwise, we check if $\textit{root}$ and $\textit{subRoot}$ are identical. If they are, we return $\text{true}$. Otherwise, we recursively check if the left or right subtree of $\textit{root}$ contains $\textit{subRoot}$.
The time complexity is $O(n \times m)$, and the space complexity is $O(n)$. Here, $n$ and $m$ are the number of nodes in the trees $root$ and $subRoot$, respectively.
1 2 3 4 5 6 7 8 91011121314151617181920
# 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 = rightclassSolution:defisSubtree(self,root:Optional[TreeNode],subRoot:Optional[TreeNode])->bool:defsame(p:Optional[TreeNode],q:Optional[TreeNode])->bool:ifpisNoneorqisNone:returnpisqreturnp.val==q.valandsame(p.left,q.left)andsame(p.right,q.right)ifrootisNone:returnFalsereturn(same(root,subRoot)orself.isSubtree(root.left,subRoot)orself.isSubtree(root.right,subRoot))
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisSubtree(root*TreeNode,subRoot*TreeNode)bool{varsamefunc(p,q*TreeNode)boolsame=func(p,q*TreeNode)bool{ifp==nil||q==nil{returnp==q}returnp.Val==q.Val&&same(p.Left,q.Left)&&same(p.Right,q.Right)}ifroot==nil{returnfalse}returnsame(root,subRoot)||isSubtree(root.Left,subRoot)||isSubtree(root.Right,subRoot)}