Given the roots of two binary trees root and subRoot, decide whether root contains a subtree identical to subRoot — same shape, same values, all the way down to the leaves. A subtree consists of a node and ALL of its descendants.
Examples
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Explanation: the matching 4 now has an extra 0 hanging under its 2 — all descendants count.
Example 3:
Input: root = [1,1], subRoot = [1]
Output: true
Example 4:
Input: root = [3,4,5,1,2], subRoot = [3]
Output: false
Constraints
1 <= nodes in root <= 2000
1 <= nodes in subRoot <= 1000
-10^4 <= Node.val <= 10^4
Prerequisites
Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree. Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.
How to think about it
1. Same Tree, Tried Everywhere Optimal
Intuition
This is the previous problem used as a subroutine: a candidate match can only start at a node whose value equals subRoot's, and from there the question is exactly "are these two trees identical". Saying that out loud — that you already have the hard part — is most of the answer.
Algorithm
1. Walk the main tree. 2. At each node, if an identical-trees check against subRoot passes, return true. 3. Otherwise try the left and right subtrees. 4. Running out of nodes means no match.
Time & Space
Time O(n*m) in the worst case, which passes at these sizes. The follow-up serializes both trees with null markers and searches for one string inside the other, O(n+m).