Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if subRoot is a subtree of root. A subtree must match in both structure and node values. Pattern focus: Trust Recursion. Check every potential root in the main tree and verify a full subtree match.

Input Format

root = main binary tree root, subRoot = subtree root

Output Format

true if subRoot is a subtree of root, otherwise false

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

true

Explanation:

The subtree rooted at node 4 matches subRoot exactly.

Example 2:

Input:

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

Output:

false

Explanation:

The candidate subtree has an extra child node, so it does not match exactly.

Loading...
Subtree of Another Tree - Binary Tree