题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/

题解

递归

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

时间复杂度 O(n)，空间复杂度 O(n)

迭代

class Solution {
    bool check(TreeNode* left, TreeNode* right) {
        queue<TreeNode*> q;
        q.push(left), q.push(right);
        while (!q.empty()) {
            left = q.front(), q.pop();
            right = q.front(), q.pop();
            if (!left && !right) continue;
            if (!left || !right || left->val != right->val) return false;
            q.push(left->left), q.push(right->right);
            q.push(left->right), q.push(right->left);
        }
        return true;
    }
public:
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};