Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return True if subRoot is a subtree of root, otherwise False.
Both trees are built from level-order arrays (with None marking a missing child) by the provided build_tree helper, so is_subtree(root, sub_root) receives TreeNode roots, not arrays.
A subtree is a node and all its descendants matching exactly.
Example
3,4,5,1,2 4,1,2
True
- Inputs:
rootcomes from the level-order array3,4,5,1,2: is the top node, its children are (left) and (right), and has children and .sub_rootcomes from4,1,2: a node with children and . - A subtree of
rootis not any connected piece of it: it is one node ofroottogether with every node below it, all the way down to the leaves. roothas five candidate subtrees, one per node: rooted at (all 5 nodes), at (), and the single leaves , , .- The candidate rooted at has value on top, on the left, on the right, and nothing below or , which is exactly the shape and values of
sub_root. So the answer isTrue. - Notice that the match must be exact to the bottom: if node in
roothad an extra child , the part rooted at would have four nodes, no node ofrootwould match, and the answer would becomeFalse.
Constraints
- 1 <= nodes in root <= 2000
- 1 <= nodes in subRoot <= 1000
- -10^4 <= Node.val <= 10^4