题目简述

        给定二叉树的根节点，判断此二叉树每层是否是对称的。

算法一: 暴力补点

时间复杂度：最好O(n)，最坏O(2n)

思路：

            对于每一层的节点都当做满节点，即把整颗树看成一个完全二叉树，然后将节点都存入vector数组里再比较。
            vector数组存的是每层从左往右的节点，第H层的节点个数：2H-1。
                    比较规则： 1 . 对称比较，即第一个和最后一个比较，第二个和倒数第二个比较......
                                       2. 两个都是空节点，则不用比较
                                       3. 两个都是非空节点，节点对应的值需相同，否则不对称。
                                       4. 一个点是非空一个点是空节点则说明不对称。

图解：


代码: 


/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot==NULL) return true;
        queue<TreeNode*> q;
        q.push(pRoot);
        while(q.size()){
            int len=q.size();
            vector<TreeNode*> res;
            int mark=0;
            for(int i=0;i<len;i++){ //将每层都遍历完
                TreeNode* t=q.front();
                q.pop();
                if(t&&t->left){
                    mark=1;
                    q.push(t->left);
                    res.push_back(t->left);
                }
                else{//补空节点，当做完全二叉树来看
                    q.push(NULL);
                    res.push_back(NULL);
                }
                if(t&&t->right){
                    mark=1;
                    q.push(t->right);
                    res.push_back(t->right);
                }
                else{//补空节点，当做完全二叉树来看
                    q.push(NULL);
                    res.push_back(NULL);
                }
            }
            if(!mark) return true; //说明这一层都是自己补的空节点，前面层都符合调节直接返回true
            int lenT=res.size()/2;
            int lenP=res.size()-1;
            for(int i=0;i<=res.size()/2;i++){//对称判断
                if(!res[i]&&!res[lenP-i]) ;
                else if(res[i]&&res[lenP-i]&&res[i]->val==res[lenP-i]->val) ;
                else{
                    return false;
                }
            }
        }
        return true;
    }

};


算法二: DFS

时间复杂度：O(n)

思路:

        分别进行对称递归，对于对称位置，再进行对称依旧是对称位置，这时我们只需比较对称位置的值即可。
                递归出口：1. 对称位置都为空说明两点对称
                                  2. 对称位置只有一个为空，则不对称
                                  3. 都不为空，则比较两个位置的值，一样则此位置对称，否者不对称。
                对称位置再找对称：DFS( lRoot -> left , rRoot-> right )；
                                                DFS( lRoot -> right , rRoot->left ) ；
                                                假设 lRoot 和 rRoot 为对称位置 ，则 lRoot -> left 与 rRoot-> right 依旧对称是对称位置，lRoot -> right 与 rRoot->left依旧是对称位置。

图解：


代码: 

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool DFS(TreeNode* lRoot,TreeNode* rRoot){
        if(!lRoot&&!rRoot) return true;//都为空说明对称点为空
        if(!lRoot||!rRoot||lRoot->val!=rRoot->val) return false;  //只有一个空，或者两个节点的值不同则不对称
        return DFS(lRoot->left,rRoot->right)&&DFS(lRoot->right,rRoot->left); //搜索下一层
    }
    bool isSymmetrical(TreeNode* pRoot) {
        return DFS(pRoot,pRoot);
    }

};