All problems

Subtree of Another Tree

Easy · tree dfs

You are given the roots of two binary trees, root and sub_root. Return True if root contains a subtree that is identical to sub_root, and False otherwise.

A subtree of root is a node of root together with all of its descendants, down to the leaves. The whole tree root also counts as a subtree of itself. "Identical" means the same shape and the same value at every matching position, so a node with extra descendants below the matching part does not count.

Examples

Example 1

Input: root = [3, 4, 5, 1, 2], sub_root = [4, 1, 2]

Output: True

The node 4 in root has children 1 and 2 and nothing else, which is exactly sub_root.

Example 2

Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], sub_root = [4, 1, 2]

Output: False

The node 4 now has a deeper descendant 0 under the 2, so its subtree is bigger than sub_root. No other node matches.

Example 3

Input: root = [1, 2, 3], sub_root = [3]

Output: True

The leaf 3 is a one node subtree, and it matches the one node tree sub_root.

Constraints