Li Kou 101: symmetric binary tree

Power button 101 topic ： Symmetric binary tree

Title Description

Give you the root node of a binary tree root , Check whether it is axisymmetric .

I/o sample

 Input ：root = [1,2,2,3,4,4,3]
 Output ：true

 Input ：root = [1,2,2,null,3,null,3]
 Output ：false

Algorithm one , Using recursion

bool  rootIsSymmetric(TreeNode *root1,TreeNode *root2)
{
    
    bool leftTrue=false,rightTrue=false;
    if(root1->val==root2->val)
    {
    
        if(root1->left&&root2->right)
        {
    
            leftTrue=rootIsSymmetric(root1->left,root2->right);
        }
        else if(!root1->left&&!root2->right)
        {
    
            leftTrue=true;
        }

        if(root1->right&&root2->left)
        {
    
            rightTrue=rootIsSymmetric(root1->right,root2->left);
        }
        else if(!root1->right&&!root2->left)
        {
    
            rightTrue=true;
        }
        return leftTrue&&rightTrue;

    }
    return false;
}


bool isSymmetric2(TreeNode *&root)
{
    
    if(!root)
    {
    
        return true;
    }
    if(root->right&&root->left)
    {
    
        if(root->left->val==root->left->val)
        {
    
           return rootIsSymmetric(root->left,root->right);
        }
        return false;
    }
    else if(!root->left&&!root->right)
    {
    
        return true;
    }
    return false;
}

Algorithm 2 , Use the official simpler recursion

bool check(TreeNode *root1,TreeNode *root2)
{
    
    if(!root1&&!root2)
    {
    
        return true;
    }
    if(!root1||!root2)
    {
    
        return false;
    }
    // Combine the above conditional judgments 
    return root1->val==root2->val&&check(root1->left,root2->right)&&check(root1->right,root2->left);
}

// The official relatively simple recursive algorithm 
bool isSymmetric3(TreeNode *&root)
{
    
    return check(root,root);
}

Algorithm three , Use queues to implement iterations

// Solution 3 , Use the idea of iteration , Use the queue to judge 

bool isSymmetric4(TreeNode *&root)
{
    
    if(!root)
    {
    
        return true;
    }
    if (!root->left&&!root->right)
    {
    
        return true;
    }

    // Create a queue save node 
    queue<TreeNode *>que;
    // Join the left child node and the right child node of the root node 
    que.push(root->left);
    que.push(root->right);

    // The existence of the next node is not verified , Only verify whether the current node exists 
    while(!que.empty())
    {
    
        // Create a temporary node to save the current node 
        TreeNode *tempLeft=que.front();
        que.pop();
        TreeNode *tempRight=que.front();
        que.pop();

        // When both nodes are empty , Continue to cycle , If one is empty, it returns false
        if(!tempLeft&&!tempRight)
        {
    
           continue;
        }
        if((!tempLeft||!tempRight)||(tempLeft->val!=tempRight->val))
        {
    
            return false;
        }


        // Queue the values of two nodes respectively 
        que.push(tempLeft->left);
        que.push(tempRight->right);

        que.push(tempLeft->right);
        que.push(tempRight->left);
    }
    return true;
    
}