TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write contains_copy(big, small) -> bool: True when some node of big, together with everything below it, is an exact copy of small: the same shape and the same values in the same places. The copy has to run all the way to the leaves, so a node whose subtree merely starts like small but has extra nodes underneath doesn't count. big itself counts as one of its own subtrees.
# big: 3 small: 4
# / \ / \
# 4 5 1 2
# / \
# 1 2
contains_copy(big, small) # True
# big2: 3
# / \
# 4 5
# / \
# 1 2
# /
# 0
contains_copy(big2, small) # False: under 4 there is an extra 0
bighas 1 to 2,000 nodes andsmallhas 1 to 200 nodes; values are arbitrary integers and repeat often.- Aim for O(n·m), where
nandmare the sizes of the two trees.
Show hint
Write a helper that says whether two trees are identical, then try it at every node of big.