added subtree of another tree solution

david-legend · david-legend · commit 9032a9256e4a · 2022-09-12T10:06:21.000Z
diff --git a/leetcode/src/binary_trees/lc_572_subtree_of_another_tree/subtree_of_another_tree.py b/leetcode/src/binary_trees/lc_572_subtree_of_another_tree/subtree_of_another_tree.py
@@ -0,0 +1,16 @@
+# Time O(mn)
+def is_subtree(root, sub_root):
+    if not sub_root: return True
+    if not root: return False
+
+    if is_same_tree(root, sub_root):
+        return True
+
+    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)
+
+def is_same_tree(s, q):
+    if not s and not q: return True
+    if s and q and s.val == q.val:
+        return (is_same_tree(s.left, q.left) and is_same_tree(s.right, q.right))
+    
+    return False
