Is One Tree Inside Another

EasyTreesDfsHash map153 tests

You are given two binary trees, root and sub.

Return true if root has a node where this node, together with everything below it, has exactly the same shape and the same values as sub. Otherwise return false.

Rules

The match must include all nodes below that node. If the node in root has a child (or a grandchild, and so on) that sub does not have, it is not a match.
The node can be root itself. So if the two trees are equal, the answer is true.
Values can repeat. Many nodes in root may have the same value as the top node of sub, and only some of them (or none) may match. Do not stop at the first node with the right value.

How the input is shown

A tree is shown as a list of values in level order: row by row from the top, and left to right in each row. null means "no child here", and nulls at the end are left out. For example, [4, 2, 7, null, 3] is a root 4 with left child 2 and right child 7, and 2 has only a right child, 3.

Your function receives the top node of each tree as a TreeNode (fields val, left, right).

Hint: first write a helper sameTree(a, b) that says if two trees are equal. Then try it at every node of root.

Examples

Example 1

Input:: [5,3,8,1,4,null,9], [3,1,4]
Output:: true

The node with value 3 has left child 1 and right child 4, and nothing else below it. That is exactly sub.

Example 2

Input:: [6,4,7,1,5,null,null,0], [4,1,5]
Output:: false

The node 4 has children 1 and 5, like sub. But in root, node 1 also has a left child 0, and in sub it has none. Everything below must match, so the answer is false.

Example 3

Input:: [1,1,3,null,null,1,null,null,2], [1,null,2]
Output:: true

Three nodes have the value 1. The top one has two children, and the left one has no children, so neither matches. The 1 under node 3 has only a right child 2, which is exactly sub.

Constraints

The number of nodes in root is between 1 and 30.
The number of nodes in sub is between 1 and 31.
0 <= Node.val <= 4
Values can repeat.

Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.