题解

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1. 递归法

class Solution {//三种方法。1、递归法。有点像#100
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;//特殊情况，为空直接返回true
        return helper(root->left,root->right);//调用递归函数
    }
    bool helper(TreeNode* p,TreeNode* q){//这一块和#100很想
        if(!p && !q) return true;//都为空返回true，对称
        if(!p || !q) return false;//一个为空则为false，不对称
        if(p->val != q->val) return false;//左右不相等则返回false
        return helper(p->left,q->right) && helper(p->right,q->left);//进行递归
    }
};

2. 栈迭代法

class Solution {//三种方法。2、栈迭代法。和先序遍历的迭代法类似
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;//特殊情况，为空直接返回true
        stack<TreeNode*> sLeft;
        stack<TreeNode*> sRight;//建立存结果的栈
        TreeNode *curLeft = root->left;
        TreeNode *curRight = root->right;//建立两个指针
        while(curLeft || !sLeft.empty() || curRight || !sRight.empty()){
            //当指针存在或栈不为空继续迭代
            //指针为空可能是到叶子节点，栈为空可能是回到了根节点，这里和先序遍历一样
            while(curLeft){//当指针存在继续迭代左子树并压入栈
                sLeft.push(curLeft);
                curLeft = curLeft->left;
            }
            while(curRight){//同上
                sRight.push(curRight);
                curRight = curRight->right;
            }
            if(sLeft.size() != sRight.size()) return false;//若栈长度不一致返回false
            curLeft = sLeft.top(); sLeft.pop();
            curRight = sRight.top(); sRight.pop();//到头了之后出栈
            if(curLeft->val != curRight->val) return false;//并检测栈顶的值。和中序遍历一样，只是中序遍历是存值，这里是进行比较。
            curLeft = curLeft->right;//再进入右子树
            curRight = curRight->left;//同上
        }
        return true;
    }
};

3. 队列迭代法

class Solution {//三种方法。3、 队列迭代法。和层次遍历有点类似（广度优先遍历BFS）一层一层比较。
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;//特殊情况，为空直接返回true
        queue<TreeNode*> qLeft;
        queue<TreeNode*> qRight;//建立两个队列存每一层的值
        qLeft.push(root->left);
        qRight.push(root->right);//存入根节点的左右子节点
        while(!qLeft.empty() && !qRight.empty()){
            //当两个队列都有值时，继续循环。注意null也会压入队列，这时队列也不为空。
            TreeNode *curLeft = qLeft.front();qLeft.pop();
            TreeNode *curRight = qRight.front();qRight.pop();//挨个取出两队列的首值。
            if(!curLeft && !curRight) continue;
            //当两个都为空时，继续循环。有可能两个对应节点都为空。
            if(!curLeft || !curRight) return false;//当其中一个为空，返回false
            if(curLeft->val != curRight->val) return false;//当对应值不想动，返回false
            qLeft.push(curLeft->left);
            qLeft.push(curLeft->right);
            qRight.push(curRight->right);
            qRight.push(curRight->left);//按对称依次为两个队列压入值。注意此时队列中可能还有上一层的值，但是队列有先进先出的性质，则下一步先计算上一层的值。
        }
        return true;
    }
};