AlgoLounge

Subtree of Another Tree

easy

LeetCode 572. 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 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.

Examples

Example 1

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

root: subRoot: 3 4 / \ / \ 4 5 1 2 / \ 1 2Output: true The subtree rooted at node 4 in root matches subRoot exactly.

Example 2

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

The subtree at node 4 has an extra child (0), so it doesn't match subRoot.

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^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

How the tests work: trees are written as level-order arrays — [1,null,2] is a root 1 with a right child 2. Your function receives real TreeNode objects.

TypeScript
Loading editor…
List of test cases (10)
Case 1
root = [3,4,5,1,2]
subRoot = [4,1,2]
Case 2
root = [3,4,5,1,2,null,null,null,null,0]
subRoot = [4,1,2]
Case 3
root = [1,2,3]
subRoot = [2]
Case 4
root = [1,2,3]
subRoot = [3]
Case 5
root = [1]
subRoot = [1]
Case 6
root = [1,2]
subRoot = [1]
Case 7
root = [1,null,2,null,3]
subRoot = [2,null,3]
Case 8
root = [1,2,3,4,5,6,7]
subRoot = [3,6,7]
Case 9
root = [1,2,3,4,5,6,7]
subRoot = [3,6,8]
Case 10
root = [1,1]
subRoot = [1]