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 root tree is in the range [1, 2000].
- The number of nodes in the subRoot tree is in the range [1, 1000].
- -104 <= root.val <= 104
- -104 <= subRoot.val <= 104
My Solution
We check equality of subtrees by checking whether two nodes have the same value and then recursively checking whether their left and right subtrees are equal. We then can do a breadth first traversal of the tree to check whether each node and the subtree are equal.
Time complexity would be O(n²) because checking for equality requires O(n) operations and we check equality n times because we check every node in the tree for equality. Space complexity would be O(n) for the space required for the breadth first traversal queue.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode n = q.removeFirst();
if (checkEqual(n, subRoot)) {
return true;
}
if (n.left != null) {
q.add(n.left);
}
if (n.right != null) {
q.add(n.right);
}
}
}
return false;
}
public boolean checkEqual(TreeNode root, TreeNode subRoot) {
if ((root == null && subRoot != null) || (root != null && subRoot == null)) {
return false;
}
if (root == null && subRoot == null) {
return true;
}
return (root.val == subRoot.val && checkEqual(root.left, subRoot.left) && checkEqual(root.right, subRoot.right));
}
}