力扣hot100：101. 对称二叉树（双指针以不同方式递归）

LeetCode：101. 对称二叉树

看了第一个样例，很容易直接层序遍历看每一层的前后是否相同。但接下来这个样例告诉你，不能这样做。

层序遍历

仔细思考会发现，层序遍历不能看本结点，但是可以看儿子结点是否对称，本质上是要判断每层的儿子是对称的。

• 在进行复杂的条件判断时，需要头脑清晰，比如这里需要区分出是否对称。那么在写条件判断的时候，可以这样思考，我们在使得条件为真时，即考虑左右子树对称时，我们只需要将对称时的情况写出：
  • 同时为空
  • 同时不为空，且值相等
• 就这两种情况，因此我们只需要把这两种情况列在if条件中即可，并不需要杂乱的各种条件都判断。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            deque<TreeNode *> deq;
            for(int i = 0;i < size;++i){
                deq.push_back(q.front());
                if(q.front()->left)
                    q.push(q.front()->left);
                if(q.front()->right)
                    q.push(q.front()->right);
                q.pop();
            }
            while(!deq.empty()){
                if((deq.front()->left && deq.back()->right && deq.front()->left->val == deq.back()->right->val)|| (!deq.front()->left && !deq.back()->right)){
                    if((deq.front()->right && deq.back()->left && deq.front()->right->val == deq.back()->left->val)|| (!deq.front()->right && !deq.back()->left)){
                        deq.pop_front();
                        if(!deq.empty()) deq.pop_back();
                    }else return false;
                }else return false;
            }
        }
        return true;
    }
};

递归

如何单独查看左右子树，由于两个递归是不能并行的，因此比较难直接进行判断。
这里采用的递归是两个指针同步反向移动。

• 由于左右子树镜像对称，那么从顶端开始，维护两个指针p、q，p向下左移时，q右移；p向下右移时,q左移。当他们每次都是相同就成功了。
• 虽然它们在同一个递归中，但是它们走的路线却是镜像的！ 并且由于左边和右边都走了，因此可以判断所有镜像的情况。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
    bool check(TreeNode * q,TreeNode * p){//递归函数，判断以p、q为根的子树，是否镜像
        if(!q && !p) return true;//都为空，则这一条路是对的
        if(!q || !p) return false;//不都为空，则不镜像对称
        if(q->val == p->val){
            if(!check(q->left, p->right)) return false;
            if(!check(q->right, p->left)) return false;
        }else return false;
        return true;
    }
};