Loading...
Loading...
You are given two binary trees root and target. Return whether target is a subtree of root.
A subtree of root is a node of root together with all of its descendants. target matches a subtree when the two have exactly the same shape and the same value at every position.
root itself counts as a subtree of root. Both trees have at least one node.
Your function receives root and target as TreeNode values. The node type is provided for you, with val, left, and right fields.
The examples below write trees as their level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how trees are displayed; the encoding and decoding are done for you.
root.target.Node.val ≤104The node holding `4` (root's left child) has left child `1` and right child `2`, exactly matching `target`'s shape and values, so `target` is a subtree of `root`.
The node holding `4` again has left child `1` and right child `2`, but that `2` node has an extra left child holding `0` that `target`'s `2` node does not have. No node in `root` matches `target` exactly, so the answer is `false`.
`root` and `target` are both the single node `1`. A tree always counts as a subtree of itself, so the answer is `true`.