题目描述：

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

输入输出样例：

示例 1：

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

示例 2：

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

提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

题解：

解题思路：

思路一（递归（深度））：

1、我们要判断对称二叉树，我们就需要判断每个对称的结点。因每次比较的对称结点是两个，所以递归函数的参数有两个，一个是左侧的对称结点，一个是右侧的对称结点。我们对对称结点进行挨个判断，判断的类型我们分为四种：
① 左右对应结点都为NULL（递归的出口：true）
② 其中一个为NULL，另一个不为NULL（递归出口：false）
③ 左右对应结点不为空，但是值不同（递归出口：false）
④ 左右对应结点不为空，且值相同（继续进行递归）

递归过程如下图所示：

2、复杂度分析：
① 时间复杂度：O(n)，这里遍历了这棵树，渐进时间复杂度为 O(n)。
② 空间复杂度：O(n)，这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

思路二（层次遍历（广度））：

1、层次遍历的思想是一层一层的进行判断，这里我们采用将对称的结点挨着放入队列的思想。我们发现这样其实就是从每层的左右最外侧结点放入队列中，然后继续将这一层的结点按左右最外侧放入，同时在从队列头部拿出两个进行比较，若满足方法一中的递归出口条件则结束层次遍历，否则将继续进行下去。

3、复杂度分析
① 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
② 空间复杂度： O(n)，这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。

代码实现

代码实现（思路一（递归（深度）））：

//方法一递归实现:判断对称二叉树
    bool isSymmetric1(TreeNode *root){
        if(root==nullptr) return true;

        return dfs(root->left,root->right);
    }

    bool dfs(TreeNode *left,TreeNode *right){
        //到达了叶子结点,则返回
        if(left==nullptr&&right==nullptr) return true;
        //排除left和right都为空的情况，若left和right其中一个为空返回false
        if(left==nullptr||right==nullptr) return false;
        //排除空的情况就可以判断结点的值
        if(left->val!=right->val) return false;

        //下面这一行代码是不能加的，会导致代码提前结束
        //if(left->val==right->val) return true;
        return dfs(left->left,right->right)&&dfs(left->right,right->left);
    }

代码实现（思路二（层次遍历（广度）））：

//方法二层次遍历实现（广度优先）：判断对称二叉树
    bool isSymmetric2(TreeNode *root){
    	//排除根节点为空的情况和左右孩子结点为空的情况
        if(root==nullptr||(root->left==nullptr&&root->right==nullptr)) return true;
        //创建队列将根节点的左右孩子结点入队
        queue<TreeNode *> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty())
        {
        	//从头部拿出两个结点进行比较
            TreeNode *left=q.front();
            q.pop();
            TreeNode *right=q.front();
            q.pop();

			//为空的结点无需加入队列
            if (left==nullptr&&right==nullptr) continue;
            //不是对称二叉树的情况
            if (left==nullptr||right==nullptr) return false;
            if (left->val!=right->val) return false;
			//将这两个结点下的的两对对称结点入队，注意入队顺序
            q.push(left->left);
            q.push(right->right);

            q.push(left->right);
            q.push(right->left);
            
        }
        
        return true;
    }

LeetCode 面试经典 150_二叉树_对称二叉树（70_101)原题链接
欢迎大家和我沟通交流(✿◠‿◠)