First of all, this is a medium difficulty problem, I think the problem can also be difficult (here is not to say that I am very cow, but haven’t I met practice algorithm for this problem is felt particularly interesting, feel to find some feeling, to solve the problem from here, I will step by step in-depth study and binary tree recursive problem), now I have no difference in the aspect of algorithm and novices, Compared with the previous simple questions, I think this is the question that will impress me after I write it!

Topic:

Input two binary trees A and B to determine whether B is A substructure of A. (Convention that an empty tree is not a substructure of any tree)

B is A substructure of A, that is, A has the same structure and node value as B.

For example: given tree A:

3/4 5/1 2 Given tree B:

4/1 returns true because B has the same structure and node values as A subtree of A.

Example 1:

Input: A = [1,2,3], B = [3,1] output: false example 2:

Input: A = [3,4,5,1,2], B = [4,1]

0 <= Number of nodes <= 10000

First thought (not necessarily right) :

First of all, pattern matching can solve the problem of substructure, and then contains function of string; I take a string, I do a preemptive loop, I iterate through all the values of the nodes (if the left and right nodes are null, it’s -1), and I get a string, and I use the contains function.

So here, I didn’t get the answer, and there’s a null pointer problem, so you can look at it for me

List<Integer> list = new ArrayList<>(); public boolean isSubStructure(TreeNode A, TreeNode B) { pre(A); String A = list.toString(); list.clear(); pre(B); String B = list.toString(); return A.contains(B)? true:false; } public void pre(TreeNode node) { if(node == null) { list.add(-1); } list.add(node.val); pre(node.left); pre(node.right); }Copy the code

Answer key:

Using the idea of recursion: we want to match the substructure, so as long as any child node in A starts from the root node of the substructure and B match the success. So let’s go through A, let’s match each node of A with B. Just one of them. The substructure that starts at a node is going to recursively match with B. How do I recurse? Of course it’s two structures left to left, right to right;

/ / A of A node to the root node to A and B match public Boolean isSubStructure {TreeNode. A, TreeNode (B) if (A = = null | | B = = null) {return false. / / the topic with specifications, an empty tree for any tree substructure} return iscontail (A, B) | | isSubStructure (a. eft, B) | | isSubStructure (A.r d.light, B); // Check whether the substructure starting from the root node of A contains the structure B, if false, then enter the recursion to determine the left, if there is no left, then determine the right. } public Boolean iscontail(TreeNode A,TreeNode B) {if(B == null) { After recursion, if the child node of B is empty, then the previous structure compared to B must match, and this is empty, indicating that the match is over. return true; } if(A == null || A.val ! = B.val) { return false; } return isContail (a.content, b.content) &&isContail (A.content, b.content); // Return true if the root node is the same and the left and right child nodes are equal.Copy the code