CodingInterview-对称的二叉树

具体的思路是使用前序、中序、后序或者层序遍历对二叉树进行遍历，在遍历的同时判断树的左右两侧是否相同。

首先来一个比较简单的使用循环的解法，这个方法使用循环和一个队列同时从两个方向对树进行层序遍历，一个从左向右加入元素，另一边从右向左加入元素。通过在遍历的时候判断元素是否相同来判断这棵树是否对称。

/*
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)
    {
        queue <TreeNode*> q;
        q.push(pRoot);
        q.push(pRoot);
        while(!q.empty()){
            TreeNode* l=q.front();
            q.pop();
            TreeNode* r=q.front();
            q.pop();
            if(l==NULL && r==NULL) continue;
            if(l==NULL || r==NULL) return false;
            if(l->val != r->val) return false;
            q.push(l->left);
            q.push(r->right);
            q.push(l->right);
            q.push(r->left);
        }
        return true;
    }
};

最后，还可以使用递归去实现。递归使用了前序遍历来实现。

/*
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 this->isSymmetric(pRoot,pRoot);
    }
    bool isSymmetric(TreeNode* pRoot1,TreeNode* pRoot2)
    {
        if(pRoot1==NULL && pRoot2==NULL) return true;
        if(pRoot1==NULL || pRoot2==NULL) return false;
        if(pRoot1->val!=pRoot2->val) return false;
        return this->isSymmetric(pRoot1->left,pRoot2->right)
            && this->isSymmetric(pRoot1->right,pRoot2->left);
    }

};

PS：这道题之前在 Leetcode 中见过，但是到这里也基本忘记的差不多了，真的是边做边忘记啊。