leetcode 101 对称二叉树

题意

给定一个二叉树及其根节点，检查是否轴对称。

做法

如果一棵树的左右子树轴对称，那么这棵树对称。于是问题转化为左右两棵子树是否镜像，同样这个问题可以拆分成【左子树的左子树和右子树的右子树是否镜像】和【左子树的右子树和右子树的左子树是否镜像】这两个子问题，可以递归解决。注意到镜像时的子问题左右已经互换了，使用两个向左右相反方向移动的指针递归遍历两棵树即可。

代码

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

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};