对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

AC代码

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

我很疑惑为什么要让空TreeNode入队,然后再判断,我不让空TreeNode入队就报段错误,自己的实例测试通过.以下是我的代码

class Solution {
public:
    queue<TreeNode*> left, right;
    bool isSymmetrical(TreeNode* pRoot)
    {
        if (pRoot == NULL) {
            return true;
        }
        if (pRoot->left == NULL && pRoot->right != NULL 
            || pRoot->left != NULL && pRoot->right == NULL
           || pRoot->left != NULL && pRoot->right != NULL && pRoot->left->val != pRoot->left->val) {
            return false;
        }
        else {
            left.push(pRoot->left);
            right.push(pRoot->right);
        }
        TreeNode* pNode = NULL;
        while (!left.empty() && !right.empty()) {
            if (left.front()->val != right.front()->val) {
                return false;
            }
            pNode = left.front();
            if (pNode->left) {
                left.push(pNode->left);
            }
            if (pNode->right) {
                left.push(pNode->right);
            }
            
            pNode = right.front();
            if (pNode->right) {
                right.push(pNode->right);
            }
            if (pNode->left) {
                right.push(pNode->left);
            }
            
            left.pop();
            right.pop();
        }
        return !(left.empty() ^ right.empty());
    }

递归的方法，看了讨论区后的一气呵成

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        if (pRoot == NULL) return true;
        return isSymmetrical(pRoot->left, pRoot->right);
    }
    
    bool isSymmetrical(TreeNode* left, TreeNode* right){
        if (left == NULL && right == NULL) return true;
        if (left == NULL || right == NULL) return false;
        if (left->val == right->val) {
            return isSymmetrical(left->left, right->right)
                && isSymmetrical(left->right, right->left);
        }
        return false;
    }
};