572. Subtree of Another Tree

Description:

https://leetcode.com/problems/subtree-of-another-tree/description/

This question is to know whether subRoot is in root or not.

If the subRoot is in the root, return True.

However, in example 2, it returns False because subRoot has unexpected child node.

This Question set it is false like example 2. 

Solution(Recursion with DFS):

Recursive method(DFS)

Before looking at identical function, we should look the cases.

In the first case, we return true when we don't have subRoot Tree.

In the second case, we return False when we don't have root.

In the last case, we compare the root and subRoot and then return True when identical function is True.

None of these case, we do recursive method left or right child node.

In identical(), we go through the both side of the two tree to compare the values.

This function is from the reference of 100. Same Tree.

It helps to judge if the two subtrees we are considering are in-fact identical. 

 

The recursion will reach out a leaf node in our tree, and return False.

We check if the current node in the tree is where our subTree is rooted at. If yes, we return True.

Ohterwise we return the value of the recursive search on the left and right children of the current node. 

 

Time Complexity: O(mn)

Space Complexity: O(mn)