力扣101题：对称二叉树

力扣101题：对称二叉树

题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

输入输出样例

输入：root = [1,2,2,3,4,4,3]
输出：true

输入：root = [1,2,2,null,3,null,3]
输出：false

算法一，使用递归

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;
}

算法二，使用官方较为精简的递归

bool check(TreeNode *root1,TreeNode *root2)
{
    
    if(!root1&&!root2)
    {
    
        return true;
    }
    if(!root1||!root2)
    {
    
        return false;
    }
    //将上面的几个条件判断合并到一块去了
    return root1->val==root2->val&&check(root1->left,root2->right)&&check(root1->right,root2->left);
}

//官方较为简洁的递归算法
bool isSymmetric3(TreeNode *&root)
{
    
    return check(root,root);
}

算法三，使用队列实现迭代

//解法三，使用迭代的思想，借助队列进行判断

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

    //建立队列保存结点
    queue<TreeNode *>que;
    //将根节点的左孩子结点和右孩子结点入队
    que.push(root->left);
    que.push(root->right);

    //并未验证下一个结点是否存在，只验证当前的结点是否存在
    while(!que.empty())
    {
    
        //建立临时结点保存当前的结点
        TreeNode *tempLeft=que.front();
        que.pop();
        TreeNode *tempRight=que.front();
        que.pop();

        //当两个结点都为空，继续循环，有一个为空则返回false
        if(!tempLeft&&!tempRight)
        {
    
           continue;
        }
        if((!tempLeft||!tempRight)||(tempLeft->val!=tempRight->val))
        {
    
            return false;
        }


        //将两个结点的值分别入队
        que.push(tempLeft->left);
        que.push(tempRight->right);

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