Blind 75 - Subtree of Another Tree
Check if root is same as subtree or root.left is same or root.right is same;
[Video]
Check if one tree is a subtree of another.
Approaches
O(n*2) time; O(1) space; 12 lines
Check if root is same as subtree or root.left is same or root.right is same;
Half the solution is from Same Tree
public boolean isSame(TreeNode one, TreeNode two){
if(one == null && two == null){
return true;
}
if(one == null || two == null){
return false;
}
return one.val == two.val && isSame(one.left, two.left) && isSame(one.right, two.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null){
return false;
}
if(isSame(root, subRoot)){
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}