题解 | #对称的二叉树#

/*
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) {
	  	return isSymmetrical1(pRoot);
        return isSymmetrical2(pRoot);
        if(pRoot==nullptr||pRoot->left==nullptr&&pRoot->right==nullptr)
             return true;
        return isSymmetrical(pRoot->left, pRoot->right);
    }
private:
    //方法一，递归
    bool isSymmetrical(TreeNode* p1, TreeNode* p2) {
        if(p1==nullptr&&p2==nullptr)
            return true;
        else if(p1!=nullptr&&p2!=nullptr){
            if(p1->val!=p2->val)
                return false;
            return isSymmetrical(p1->left,p2->right)&& isSymmetrical(p1->right,p2->left);
        }
        return false;
    }
    //方法二，双端队列迭代
    bool isSymmetrical1(TreeNode* pRoot) {
        deque<TreeNode*> tmp;
        deque<TreeNode*> child;
        if (pRoot == nullptr || pRoot->left == nullptr && pRoot->right == nullptr)
            return true;
        //若根节点的两个子节点不全不为空
        if (!(pRoot->left != nullptr && pRoot->right != nullptr))
            return false;
        tmp.push_back(pRoot->left);
        tmp.push_back(pRoot->right);
        while (!tmp.empty()) {
            while (!tmp.empty()) {
                TreeNode* p1 = tmp.front();
                tmp.pop_front();
                TreeNode* p2 = tmp.back();
                tmp.pop_back();
                if(p1->val!=p2->val)
                    return false;
                bool h1 = p1->left == nullptr;
                bool h2 = p1->right == nullptr;
                bool h3 = p2->left == nullptr;
                bool h4 = p2->right == nullptr;
                if(h1!=h4||h2!=h3)
                    return false;
                if(!h1&&!h4){
                    child.push_front(p1->left);
                    child.push_back(p2->right);
                }
                if(!h2&&!h3){
                    child.push_front(p1->right);
                    child.push_back(p2->left);
                }
            }
            tmp.swap(child);
        }
        return true;
    }
    //方法三，0来补位的迭代
    bool isSymmetrical2(TreeNode* pRoot) {
        deque<TreeNode*> tmp;
        deque<TreeNode*> child;
        if (pRoot == nullptr || pRoot->left == nullptr && pRoot->right == nullptr)
            return true;
        //若根节点的两个子节点不全不为空
        if (!(pRoot->left != nullptr && pRoot->right != nullptr))
            return false;
        tmp.push_back(pRoot->left);
        tmp.push_back(pRoot->right);
        while (!tmp.empty()) {
            while (!tmp.empty()) {
                TreeNode* p1 = tmp.front();
                tmp.pop_front();
                TreeNode* p2 = tmp.back();
                tmp.pop_back();
                if(p1==nullptr&&p2==nullptr)
                    continue;
                if(p1!=nullptr&&p2!=nullptr){
                    if(p1->val!=p2->val)
                        return false;
                    child.push_front(p1->left);
                    child.push_back(p2->right);
                    child.push_front(p1->right);
                    child.push_back(p2->left);
                }
                else 
                    return false;
            }
            tmp.swap(child);
        }
        return true;
    }
};

一种递归和两种迭代