Subtree of Another Tree

Subtree of Another Tree

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 tree is a tree that consists of a node in tree and all of this node's descendants.

Examples

Example 1:

Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output: true

      3
     / \
    4   5       4
   / \         / \
  1   2       1   2

Example 2:

Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
Output: false

        3
       / \
      4   5       4
     / \         / \
    1   2       1   2
       /
      0

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

Expected Complexity

• Time: O(m * n) where m and n are sizes of the two trees
• Space: O(h) where h is the height of the root tree