Subtree

You are given two binary trees root, and target. Return whether target is a subtree of root — that is, whether there’s a node in root that is identically same in values and structure as root including all of its descendants.

https://binarysearch.com/problems/Subtree

Examples

Example 1

Input

• root =

• target =

Output

• answer = True

Example 2

Input

• root =

• target =

Output

• answer = False

Example 3

Input

• root =

• target =

Output

• answer = True

Solution