Subtree of Another Tree
Easy
Tree
Depth-First Search
String Matching
Binary Tree
Hash Function
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 of `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. The tree `tree` could also be considered as a subtree of itself.
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
Example 3
Input: root = [1,1], subRoot = [1]
Output: true

Constraints

  • •The number of nodes in the root tree is in the range [1, 2000].
  • •The number of nodes in the subRoot tree is in the range [1, 1000].
  • •-10⁴ <= root.val, subRoot.val <= 10⁴
Time Complexity
O(m*n)
Space Complexity
O(m+n)
14
Case 1
Input: [3,4,5,1,2] [4,1,2]
Expected: true
Case 2
Input: [3,4,5,1,2,null,null,null,null,0] [4,1,2]
Expected: false
Case 3
Input: [1,1] [1]
Expected: true