[数据结构与算法]LeetCode101 对称二叉树

递归方法：

• 递归函数仅考虑同一父节点的左右子节点之间的对称关系
  – 同为空指针，true
  – 其中一个为空指针，false
  – 数值是否相同 + 左子树是否对称 + 右子树是否对称 = 是否满足对称性
  (镜面对称，两个节点的移动相反，一个向左，一个向右)

迭代方法：

• 每次将左右节点一起加入队列中
• 每次取前两个进行比较
• 再将这两个节点的子节点加入队列

附上代码：

递归法

class Solution {
public:
    bool check (TreeNode* p1, TreeNode* p2){
        if(!p1 && !p2) return true;
        if(!p1 || !p2) return false;
        return p1->val == p2->val && check(p1->left, p2->right) && check(p1->right, p2->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return check(root->left, root->right);
    }
};

迭代法

class Solution {
public:
    
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        que.push(root);
        while(que.size() > 0) {
            TreeNode* n1 = que.front(); que.pop();
            TreeNode* n2 = que.front(); que.pop();
            if(!n1 && !n2) continue;
            if(!n1 || !n2 || (n1->val != n2->val)) return false;
            que.push(n1->left);
            que.push(n2->right);
            que.push(n1->right);
            que.push(n2->left);
        }
        return true;
    }
};