题解 | #对称的二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
#include <stack>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    // 对称二叉树，根左右与根右左访问结果一样
    bool visit(TreeNode* r1, TreeNode* r2)
    {   
        // 两边都为空时，对称
        if(!r1 && !r2)  return true;
        // 一侧为空或者值不等时，不对称
        if (!r1 || !r2 || r1->val != r2->val) return false;
        // 迭代下一组, 根左右（r1 左 右）与根右左（r2 右 左）方式遍历
        if(visit(r1->left, r2->right)&&visit(r1->right, r2->left)) return true;
        return false;
    }

    bool isSymmetrical(TreeNode* pRoot) {
        // write code here
        if (!pRoot) return true;    // 为空时，则表示对称
        // return visit(pRoot->left, pRoot->right);    // 方式1，迭代方式判断

        // 方式2，层序遍历方式，队列
        queue<TreeNode*> q_l;
        queue<TreeNode*> q_r;
        q_l.push(pRoot->left);
        q_r.push(pRoot->right);
        while (!q_l.empty() && !q_r.empty()) {
            TreeNode* l = q_l.front();
            q_l.pop();
            TreeNode* r = q_r.front();
            q_r.pop();
            // 左右节点都为空节点，则为对称，但需要继续往下层序遍历
            if(!l && !r) continue;       //return true;
            // 一方不为空，或者值不等，则不对称
            if(!l || !r || l->val != r->val) return false;
            // 重新入队,q_l为左侧开始层序，q_r为右侧开始层序遍历
            q_l.push(l->left);
            q_l.push(l->right);
            q_r.push(r->right);
            q_r.push(r->left);
        }
        return true;    // 找不到不对称情况，那么则认为对称

    }
};