给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

**输入：**root = [1,2,2,3,4,4,3]
**输出：**true

示例 2：

**输入：**root = [1,2,2,null,3,null,3]
**输出：**false

提示：

树中节点数目在范围 [1, 1000] 内

-100 <= Node.val <= 100

**进阶：**你可以运用递归和迭代两种方法解决这个问题吗？

递归法：从根开始递归比较左节点和右节点，

如果相等则继续递归比较左节点的左孩子和右节点右孩子、左节点的右孩子和右节点的左孩子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (root == nullptr)
            return true;
        return isSym(root->left, root->right);
    }
    bool isSym(TreeNode *left, TreeNode *right) {
        if (left == nullptr && right == nullptr)
            return true;
        if (left == nullptr || right == nullptr)
            return false;
        return left->val == right->val && isSym(left->left, right->right) &&
               isSym(left->right, right->left);
    }
};

迭代法：类似层序遍历，注意入队节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (root == nullptr)
            return true;
        queue<TreeNode *> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty()) {
            TreeNode *left = q.front();
            q.pop();
            TreeNode *right = q.front();
            q.pop();
            if (left == nullptr && right == nullptr)
                continue;
            if (left == nullptr || right == nullptr)
                return false;
            if (left->val != right->val)
                return false;
            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
        }
        return true;
    }
};