Leetcode exercise - Sword finger offer 26 Substructure of tree

1. Title Description

The finger of the sword Offer 26. The substructure of a tree
Input two binary trees A and B, Judge B Is it right? A Substructure of .( A convention empty tree is not a substructure of any tree )

B yes A Substructure of , namely A There are emergence and B Same structure and node values .

for example :
Given tree A:

    3
   / \
  4   5
 / \
1   2

Given tree B：

  4 
 /
1

return true, because B And A A subtree of has the same structure and node values .

Example 1：

 Input ：A = [1,2,3], B = [3,1]
 Output ：false

Example 2：

 Input ：A = [3,4,5,1,2], B = [4,1]
 Output ：true

2. Problem solving ideas and codes

2.1 Their thinking

Question request judgment B Is it A The subtree of , So first we need to be in A Find B Root node of , Then start from the root node to judge whether the nodes are the same . So the topic becomes two steps ： stay A Search for B Root node of the same node 、 Take this node as the root node and B Compare and judge whether they are the same in turn . Take the topic as an example 2 To illustrate .
First, in the A Find and B Points with the same root node value

stay A After finding the node in , Take this node as the root node and B Compare from the root node , until B Traverse complete

It should be noted that , The values of nodes in the title may be the same , So you need to A Find each node , And make a comparison every time you find one .

2.2 Code

class Solution {
    
    boolean ans = false;

    public boolean isSubStructure(TreeNode A, TreeNode B) {
    
        if (B == null) {
    
            return false;
        }
        find(A, B);
        return ans;
    }
	//  Compare whether the two trees are the same 
    public boolean compare(TreeNode root, TreeNode compareNode) {
    
        if (root == null) {
    
            return compareNode == null;
        }
        if (compareNode == null) {
    
            return true;
        }
        if (root.val != compareNode.val) {
    
            return false;
        }
        //  Compare the leftmost subtree of the current node 
        boolean p1 = compare(root.left, compareNode.left);
        //  Compare the right subtree of the current node 
        boolean p2 = compare(root.right, compareNode.right);
        return p1 & p2;
    }

    public void find(TreeNode root, TreeNode compareNode) {
    
        if (root == null) {
    
            return;
        }
        if (root.val == compareNode.val) {
    
        	//  When the value of the current node is the same as that of the tree head node for comparison , Compare 
            boolean compare = compare(root, compareNode);
            ans |= compare;
        }
        //  Find the left subtree 
        find(root.left, compareNode);
        //  Find the right subtree 
        find(root.right, compareNode);
    }
}

2.3 test result

Pass the test

3. summary

• According to the requirements of the topic, we need to search and compare the tree
• Every time you find a node with the same value, you need to make a comparison