Subtree of Another Tree

easy

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 as subRoot, and false otherwise.

A subtree of a binary tree is a tree consisting of a node in it and all of that node's descendants.

Test Cases

Copy an input into the main harness and Run to verify

Input

root = [3,4,5,1,2], subRoot = [4,1,2]

Expected Output

true

Input

root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]

Expected Output

false

Explanation: The extra node 0 means the subtree is not an exact match.

Constraints

The number of nodes in root is in the range [1, 2000].
The number of nodes in subRoot is in the range [1, 1000].
-10^4 <= Node.val <= 10^4

Hints

Hint 1 — click to reveal

This builds directly on Same Tree — at each node, ask whether the trees match exactly from there.

Hint 2 — click to reveal

A subtree must include *all* descendants, so a partial match does not count.

Java Compiler