572. Subtree of Another Tree
Easy51.3% acceptance1,226,812 / 2,393,196 submissions
Asked by 8 companies
Topics
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
Constraints:
- The number of nodes in the
roottree is in the range[1, 2000]. - The number of nodes in the
subRoottree is in the range[1, 1000]. -104 <= root.val <= 104-104 <= subRoot.val <= 104
Hints
Hint 1
Which approach is better here- recursive or iterative?
Hint 2
If recursive approach is better, can you write recursive function with its parameters?
Hint 3
Two trees s and t are said to be identical if their root values are same and their left and right subtrees are identical. Can you write this in form of recursive formulae?
Hint 4
Recursive formulae can be:
isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)