Subtree of Another Tree

You get two binary trees, root and subRoot. Return true if subRoot appears inside root as a subtree, and false if not.

A subtree is one node of root with everything below it. It goes all the way down to the leaves. No branch may be cut off.

The tree subRoot appears in root if one subtree matches it exactly. It must have the same shape and the same value in each spot. The whole of root also counts as a subtree.

In the examples, each tree is written row by row from the top. Each row goes left to right. None marks a missing child.

Example 1:

      root          subRoot
       1               4
      / \             / \
     7   4           3   6
        / \
       3   6

Input: root = [1,7,4,None,None,3,6], subRoot = [4,3,6]
Output: true
Explanation: The right child of the root is 4.
Below it are 3 and 6, and nothing more.
That is exactly subRoot.

Example 2:

      root          subRoot
       1               4
      / \             / \
     7   4           3   6
        / \
       3   6
      /
     5

Input: root = [1,7,4,None,None,3,6,5], subRoot = [4,3,6]
Output: false
Explanation: The 4 in root has 3 and 6 below it.
But that 3 also has a child, 5.
The subtree under 4 must keep the 5, so it doesn't match.
No other node holds 4.

Example 3:

      root          subRoot
       5               5
      / \             /
     3   5           3
        /
       3

Input: root = [5,3,5,None,None,3], subRoot = [5,3]
Output: true
Explanation: The top 5 also has a right child, so it doesn't match.
The lower 5 has only a left child, 3.
That subtree matches.

Constraints:

• root has 1 to 2,000 nodes.
• subRoot has 1 to 1,000 nodes.
• Each value is a whole number from -10,000 to 10,000.
• Each tree is at most 400 levels deep.