思路

题目分析

1. 题目给出一棵二叉树
2. 我们需要返回判断这棵二叉树是否为左右对称的
3. 这不仅要求我们要树的形状对称，还要求结点的数值也对称，并且只要求左右沿着根节点镜像即可

• 方法一：递归
  • 我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，pp 指针和 qq 指针一开始都指向这棵树的根，随后 pp 右移时，qq 左移，pp 左移时，qq 右移。每次检查当前 pp 和 qq 节点的值是否相等，如果相等再判断左右子树是否对称。
• 方法二：迭代
  • 首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

方法一：递归

class Solution {
public:
    bool check(TreeNode*p,TreeNode*q){
        if(p==NULL&&q==NULL) return true;			// 如果两个节点都是NULL则返回真
        if(p==NULL||q==NULL) return false;			// 如果一个节点存在另一个结点为NULL直接返回false
        return p->val==q->val&&check(p->left,q->right)&&check(p->right,q->left); //在两个结点都存在的情况下，判断值是否相等，并且按照对称的方向进行递归调用，左侧的左指针对应右侧的右指针，沿着这个对应的方向访问
    }

    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return true;					// 判断根节点
        return check(root->left,root->right);		  // 递归入口
    }
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，所有的结点都要遍历一遍
• 空间复杂度：$O(logN)O(logN)$，递归调用的栈空间消耗

方法二：迭代

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);					// 队列每两个位置存储一对即将需要判断是否对称的结点结点
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;				// 如果都为NULL则继续下一轮循环，说明可能为True
            if ((!u || !v) || (u->val != v->val)) return false;	//如果不对称则直接返回false
			// 对称地继续压入待判断的左右节点
            q.push(u->left); 		
            q.push(v->right);

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

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，每个节点都要访问
• 空间复杂度：$O(logN)O(logN)$，队列中最大占用的空间不超过树的一层的结点数量，量级为$O(logN)O(logN)$