对称二叉树

1
class Solution {
2
public:
3
    bool isSymmetric(TreeNode* root) {
4
        if (!root) return true;
5
        return isMirror(root->left, root->right);
6
    }
7
private:
8
    bool isMirror(TreeNode* L, TreeNode* R) {
9
        if (!L && !R) return true;  // 都为空，匹配
10
        if (!L || !R) return false; // 一个空一个不空，不匹配
11

12
        // 值匹配 且 交叉位匹配
13
        return (L->val == R->val)
14
            && isMirror(L->left, R->right)
15
            && isMirror(L->right, R->left);
16
    }
17
};

1
#include <queue>
2

3
class Solution {
4
public:
5
    bool isSymmetric(TreeNode* root) {
6
        if (!root) return true;
7

8
        queue<TreeNode*> q;
9
        q.push(root->left);
10
        q.push(root->right);
11

12
        while (!q.empty()) {
13
            TreeNode* L = q.front(); q.pop();
14
            TreeNode* R = q.front(); q.pop();
15

16
            if (!L && !R) continue;
17
            if (!L || !R || L->val != R->val) return false;
18

19
            // 按照镜像顺序成对入队
20
            q.push(L->left);   // 左的左
21
            q.push(R->right);  // 右的右
22
            q.push(L->right);  // 左的右
23
            q.push(R->left);   // 右的左
24
        }
25
        return true;
26
    }
27
};