Sword finger offer 26: substructure of tree

The substructure of a tree

subject ：

Ideas ：

Set recursion in recursion ;
A subtree is not necessarily A root node root1 Start , Traverse the preamble A Each node of --------- recursive 1
When traversing A The current node of root1 As a starting point , Judge B Whether it's the current root1 The subtree of --------- recursive 2

Every time I traverse from A when root1 set out , Call recursion 2 To judge B Is it root1 The subtree of , if root1 and B The root nodes of are not equal , Then there is no need to recurse , direct false, That is, the root nodes of the current two trees are different ;
When root1 and root2 Isochronous , Just started to recurse downward

Java Realization ：

import java.util.*;
public class Solution {
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    
        if(root1==null || root2==null){
    
            return false;  //  Filter first A、B There is null All back to false
        }
        // The former sequence traversal 
        // Traverse A, At present root1 As a starting point , To judge B Is it root1 The subtree of , 
        boolean a=check(root1,root2);
        // Recursive traversal A Child nodes of 
        boolean left=HasSubtree(root1.left,root2);
        boolean right=HasSubtree(root1.right,root2);
        return a || left || right; //  Either case true be true
         
    }
    // Judge B Is it A subtree 
    Boolean check(TreeNode root1,TreeNode root2){
    
        if(root1==null && root2==null){
     // Termination conditions , incoming A B It can't all be null, The front has been filtered out 
            return true;
        }
        if(root1!=null && root2==null){
     //A It's not over yet ,B It's gone , explain B yes A Part of , be true ！！！
            return true;
        }
        if(root1==null && root2!=null){
      //A It's all done ,B also ,  explain B There are redundant ,
            return false;
        }
        // Traversing the tree   Before the order 
        if(root1.val!=root2.val){
    
            return false;
        }
        Boolean left=check(root1.left,root2.left);
        Boolean right=check(root1.right,root2.right);
        return left && right;
    }
}