LeetCode 101 对称二叉树

101.对称二叉树

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

1.1 DFS实现

此处的轴对称问题，重点在于要明白如何进行比较，对于两个子树，首先是对比子树的根节点是否相等，接下来的对比过程应该是对比左边的左孩子和右边的右孩子是否相等，然后再左右交换。重点是在于明白对比的过程，然后就能否简单的基于递归实现。

class Solution {
public:
    bool Symmetric(TreeNode *node1,TreeNode *node2){
        if(node1 && node2 && node1->val==node2->val){  
            return Symmetric(node1->left,node2->right)&&Symmetric(node1->right,node2->left);
        }
        if(!node1&&!node2){
            return true;
        }
        return false;
    }
    bool isSymmetric(TreeNode* root) { // 基于DFS实现
       if(!root) return true;
       return Symmetric(root->left,root->right);
    }
};

1.2 基于迭代实现

使用一个队列，首先将根节点入队两次，每次出队两个连续的元素，再入队时采取交替入队的当时，假设node1和node2是队列中的初始状态，那么先两个元素出队，然后node1->left入队，node2->right入队。（本质上还是在利用轴对称的特性） 此处额外需要注意的就是对左右子树的是否为空需要进行额外的判断。在出队时进行值的判断，在入队时主要进行是否为空的判断。

class Solution {
public:
    bool isSymmetric(TreeNode* root) { // 基于BFS实现
       queue<TreeNode*> q;
       if(!root) return true;
       q.push(root);
       q.push(root);
       while(!q.empty()){
           TreeNode *node1=q.front();
           q.pop();
           if(q.empty()) return false;
           TreeNode *node2=q.front();
           q.pop();
           if(node1->val!=node2->val) return false;
           if(node1->left&&node2->right){
                q.push(node1->left);
                q.push(node2->right);
           }else{
               if(!node1->left&&node2->right||node1->left&&!node2->right){
                   return false;
               }
           }
           if(node1->right&&node2->left){
                q.push(node1->right);
                q.push(node2->left);
           }else{
               if(!node1->right&&node2->left||node1->right&&!node2->left){
                   return false;
               }
           }
       }
       return true;
    }
};