题解 | #对称的二叉树#

    //思路，可以用层序遍历，每一层的结果在数组中一定是镜像的。
    //判断时直接在数组中预判下一层即可。
    bool isSymmetrical_v1(TreeNode* pRoot) {
        if(pRoot==NULL)
            return true;
        queue<TreeNode*>q;
        vector<TreeNode*>children;
        int parent=1;
        int childNum=0;
        q.push(pRoot);
        while(!q.empty())
        {
            TreeNode* Current=q.front();
            q.pop();
            parent--;
            
            children.push_back(Current->left? Current->left:NULL);
            children.push_back(Current->right? Current->right:NULL);
            
            childNum+=2;
            //本层的节点都出队了，即下一层的节点都进入数组了
            if(parent==0)
            {
                for(int i=0;i<childNum/2;i++)
                {
                    //如果都不为空
                    if( children[i] && children[childNum-i-1] )
                    {
                        if(children[i]->val!=children[childNum-i-1]->val){
                            return false;
                        }
                        //如果都为空
                    }
                    else if((!children[i]) && (!children[childNum-i-1]))
                    {
                        continue;
                    }
                    else//如果一边为空一边不为空。
                    {
                        return false;
                    }
                }
                for(auto child:children)
                {
                    if(child==NULL){
                        childNum--;
                        continue;
                    }
                    q.push(child);
                }
                //对状态重新初始化。
                children.clear();
                parent=childNum;
                childNum=0;
            }
        }
        return true;
    }
    //从排行榜抄来的递归思路。
    bool isSymmetrical(TreeNode* pRoot) {
    //思路：辅助递归函数比较两节点是否符合，符合就递归往下
        if(!pRoot) return true;
        return helper(pRoot->left,pRoot->right);
    }
    bool helper(TreeNode* left,TreeNode* right){
        //如果目标的两个节点都不存在，那肯定是对称的
        if(!left && !right) return true;
        //如果目标的两个节点只有其中一个存在，或是即使是存在了但值不相等，则不对称
        if((!left || !right || left->val != right->val)) return false;
        //让左节点的左节点与右节点的右节点比较，让左节点的右节点与右节点的左节点比较
        //这样才能也满足镜像。
        return helper(left->left,right->right) && helper(left->right,right->left);
    }