Subtree of another tree
You get the roots of two binary trees, root and sub_root. Return True if some node of root, together with everything below it, is the same tree as sub_root: same shape and same values. Otherwise return False.
The match must reach the bottom: the node's whole subtree (the node and everything below it) has to equal sub_root, not only its top rows. The top node of root is a candidate too, so a tree contains itself.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [1, 2, 3, 4, 5], sub_root = [2, 4, 5]OutputTrueNode 2 has children 4 and 5 and nothing below them, exactly like sub_root.
root = [1, 2, 3, 4, 5, None, None, 6], sub_root = [2, 4, 5]OutputFalseNode 2 looks right at the top, but its child 4 has a child 6 that sub_root does not have.
root = [1, 1], sub_root = [1]OutputTrueThe leaf 1 matches. The root 1 does not, because it has a child.
1 ≤ number of nodes in root ≤ 2,000
1 ≤ number of nodes in sub_root ≤ 1,000
-104 ≤ node values ≤ 104
Each tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.