You get the roots of two binary trees, root and subRoot. Return true if subRoot appears somewhere inside root as one of its subtrees, and false otherwise.
A subtree of root is any node of root together with everything below it, all the way down to the leaves. root counts as a subtree of itself. subRoot appears in root when some subtree has exactly the same shape as subRoot and the same value in every position. It is not enough for subRoot to match only the top part of a subtree: the subtree may not have any extra nodes hanging below.
The node 3 in root, with its children 1 and 5, is exactly subRoot.
The top of the subtree at 3 looks like subRoot, but below it 5 has a child 6, which subRoot does not have.
The root's value is 7, but its subtree also holds -4 and 9. The only one-node subtrees are the leaves -4 and 9.
Constraints
root has between 1 and 2000 nodes.subRoot has between 1 and 1000 nodes.-10⁴ <= Node.val <= 10⁴ in both trees.If subRoot appears in root, the match starts at a node of root holding the same value as subRoot's root. From that node down, the two must be identical trees, all the way to the leaves.
If subRoot appears in root, the match has a top: some node of root where the copy of subRoot begins. From that node down, the two trees must be identical: the same values in the same places, the same missing children, and nothing extra hanging below. So the question splits in two: which node is the top, and is the tree under it identical to subRoot?
Time O(n + m)Space O(n + m)
The full walkthrough and code are part of Premium
true