Leetcode sword finger offer 26 Substructure of tree

Title Description ：

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 .

Examples ：

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

Limit ：

0 <= Number of nodes <= 10000

Their thinking ：

If tree B It's a tree. A Substructure of , Then the root node of the substructure may be a tree A Any node of . therefore , Judgment tree B Is it a tree A Substructure of , The following two steps need to be completed ：

    Preorder traversal tree A Every node in nA​ ;（ The corresponding function isSubStructure(A, B)）
    Judgment tree A in With nA​ The subtree of the root node Whether to include trees B .（ The corresponding function recur(A, B)）

Algorithm flow ：

    Noun regulation ： Trees A The root node of is recorded as node A , Trees B The root node of is called node B .

recur(A, B) function ：

    Termination conditions ：
        When node B It's empty ： Description tree B Matching completed （ Cross leaf node ）, Therefore return true ;
        When node A It's empty ： It means you've crossed the tree A Leaf node , That is, the match failed , return false ;
        When node A and B The value is different. ： Description matching failed , return false;
    Return value ：
        Judge A and B Are the left child nodes equal , namely recur(A.left, B.left) ;
        Judge A and B Whether the right child nodes of are equal , namely recur(A.right, B.right) ;

isSubStructure(A, B) function ：

    Special case handling ： When Trees A It's empty or Trees B It's empty when , Go straight back to false ;
    Return value ： If tree B It's a tree. A Substructure of , It must satisfy one of the following three situations , So use or || Connect ;
        With node A The subtree of the root node Inclusion tree BBB , Corresponding recur(A, B);
        Trees B yes Trees A The left subtree Substructure of , Corresponding isSubStructure(A.left, B);
        Trees B yes Trees A Right subtree Substructure of , Corresponding isSubStructure(A.right, B);

        above 2. 3. It's actually about trees A do The first sequence traversal .

Java Program ：

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}