Leetcode 101. symmetric binary tree & 100. same tree & 572. Subtree of another tree

101. Symmetric binary tree

title ： recursive

The recursive trilogy is introduced below ：

1. Determine the parameters and return values of recursive functions

    Because we want to compare whether the two subtrees of the root node flip each other , Then judge whether the tree is a symmetric tree , So the two trees to compare , Parameters are also left subtree nodes and right subtree nodes . The return value is naturally boolean type .
   
    The code is as follows ：
   
   bool compare(TreeNode left, TreeNode right)
   

2. Determine termination conditions

    To compare two nodes with different values , First of all, we should make clear the situation that the two nodes are empty ！ Otherwise, the null pointer will be operated when comparing values later .
   
    When the node is empty, there are ：（ Note that we are not comparing the left child and the right child , So I call it the left node and the right node ）
   1.  Left and right are empty , symmetry , return true
   2.  Left node is empty , The right node is not empty , Asymmetry ,return false
   3.  Left not empty , Right is empty. , Asymmetry  return false
   4.  Left and right are not empty , Compare node values , If it's different, it's just return false
   
    At this time, the left and right nodes are not empty , And the values are different, we also deal with .
   
    The code is as follows ：
   if (left == NULL && right != NULL) return true;
   if (left== NULL || right == NULL) return false;
   if (left->val != right->val) return false;
   
    Let's rule out all the above situations , The rest is   Left and right nodes are not empty , And the same value .
   

3. Determine the logic of monolayer recursion

    At this point, we enter the logic of single-layer recursion , The logic of single-layer recursion is to deal with   Left and right nodes are not empty , And the same value .
   
        Compare whether the outside of the binary tree is symmetrical ： The left child of the left node is passed in , The right child of the right node .
        Compare whether the internal measurement is symmetrical , Pass in the right child of the left node , The left child of the right node .
        If both sides are symmetrical, return to true , If one side is asymmetric, it returns false .
   
    The code is as follows ：
   
   bool outside = compare(left->left, right->right);   //  The left subtree ： Left 、  Right subtree ： Right 
   bool inside = compare(left->right, right->left);    //  The left subtree ： Right 、  Right subtree ： Left 
   bool isSame = outside && inside;                    //  The left subtree ： in 、  Right subtree ： in （ Logical processing ）
   return isSame;
   

Code implementation ：

class Solution {
    
    public boolean isSymmetric(TreeNode root) {
    
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right){
    
        if(left == null && right == null){
    
            return true;
        } 
        if(left == null || right == null){
    
            return false;
        } 
        if(left.val != right.val){
    
            return false;
        }
			 //  Compare the outside of the tree 
        boolean outside = compare(left.left, right.right);
        //  Compare the inside of the tree 
        boolean inside = compare(left.right, right.left);

        return outside && inside;
    }
}

100. Same tree

Code implementation ：

class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
    
        return compare(p, q);
    }

    private boolean compare(TreeNode p, TreeNode q){
    
        if(left == null && right == null){
    
            return true;
        } 
        if(left == null || right == null){
    
            return false;
        } 
        if(left.val != right.val){
    
            return false;
        }

        //  Compare the left side of the two trees 
        boolean outCompare = compare(p.left, q.left);  //  A tree compares the outside and the inside ,  The two trees are compared on the same side 
        //  Compare the right side of the two trees 
        boolean inCompare = compare(p.right, q.right);

        return outCompare && inCompare;
    }
}

572. The subtree of another tree

Code implementation ( Sequence traversal + recursive )：

class Solution {
    
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    
        //  Declare a secondary queue 
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
    
            int len = queue.size();
            while(len > 0){
    
                TreeNode tempNode = queue.poll();
                if(compare(tempNode, subRoot)){
      //  Compare compare(tempNode, subRoot)  Not compare(root, subRoot)
                    return true;
                }
                if(tempNode.left != null) queue.offer(tempNode.left);
                if(tempNode.right != null) queue.offer(tempNode.right);
                len--;
            }
        }

        return false;

    }

    public boolean compare(TreeNode p, TreeNode q){
    
        if(p == null && q == null){
    
            return true;
        }

        if(p == null || q == null){
    
            return false;
        }

        if(p.val != q.val){
    
            return false;
        }

        return compare(p.left, q.left) && compare(p.right, q.right);
    }
}