Solution to Substructure In Tree from Jobdu

9 Aug

Question (in Chinese):

Question Name: Substructure In Tree

Question Description: Give two binary tree, check whether the latter one is a substructure of the first one.

Input: the input might contain multiple test cases. Inside each test case, the first line includes two interger N and M (0 <= N, M <= 1000), saying the size of the first and second binary tree respectively. The second line includes N integers, as the value of each node in the first tree (the first node is the root node). Then the following N lines have three different formations. The i(th) line is
1. Contains only one integer: 0, means the (i)th node has no child; OR
2. Contains two integers: 1 and another integer LS, means the (i)th node only have (LS)th node as its left son; OR
3. Contains three integers: 2 LS RS, means the  (i)th node has (LS)th node as its left son, and (RS)th node as its right son.
After that,
the following (M+1) lines are the information in the same formation about the second tree..
PS: both the line NO. and the nodes are 1-based index.

Output: “NO” if the second tree is not a substructure of the first one. Otherwise, print out “YES”. An empty tree is not a substructure of any tree.

The following is a recursive solution.

Leave a Reply

Your email address will not be published. Required fields are marked *