给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1

/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1

/ \
2 2
\ \
3 3
说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

递归的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode *l, TreeNode *r) {
        if (!l || !r) return !l && !r; // 是否同时为NULL
        return l->val == r->val && dfs(l->left, r->right) && dfs(l->right, r->left);
    }

    bool isSymmetric(TreeNode *root) {
        return !root || dfs(root->left, root->right);
    }
};

迭代的代码（队列实现）

思路：层次遍历，每次取出两个指针，把它的儿子节点加入进来，注意加的顺序，先加左右，再加右左

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        queue < TreeNode * > q;
        auto t1 = root->left, t2 = root->right;
        q.push(t1), q.push(t2);
        while (!q.empty()) {
            t1 = q.front(), q.pop();
            t2 = q.front(), q.pop();
            if (!t1 && !t2) continue;
            if (!t1 || !t2 || t1->val != t2->val) return false;
            q.push(t1->left), q.push(t2->right);
            q.push(t1->right), q.push(t2->left);
        }
        return true;
    }
};

迭代写法（栈实现）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;

        stack<TreeNode*> left, right;
        auto lc = root->left, rc = root->right;
        while (lc || rc || left.size())
        {
            while (lc && rc)
            {
                left.push(lc), right.push(rc);
                lc = lc->left, rc = rc->right;
            }

            if (lc || rc) return false;
            lc = left.top(), left.pop();
            rc = right.top(), right.pop();

            if (lc->val != rc->val) return false;
            lc = lc->right, rc = rc->left;
        }

        return true;
    }
};