对称二叉树判断-CSDN博客

本文链接：https://blog.csdn.net/ifreewolf_csdn/article/details/108303042

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

题解

题目描述：给定一颗二叉树，判断此二叉树是否为对称二叉树。

根据上图可知：若满足对称二叉树，必须满足：

1. L->val == R->val
2. L->left->val == R->right->val
3. L->right->val == R->left->val

设置一个递归函数isSame(r1, r2),表示如果对称，返回true，否则返回false因此可以自顶向下，递归求解即可。

递归终止条件：r1==nullptr && r2==nulllptr, 直接返回true，否则，如果只有一个为nullptr，返回false
下一步递归：如果r1->val == r2->val, 则isSame(root1->left, root2->right) && isSame(root1->right, root2->left);

代码如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool dfs(TreeNode* left, TreeNode * right){
        if(!left && !right) return true;
        if(!left || !right) return false;
        return left->val == right->val &&
            dfs(left->left, right->right) &&
            dfs(left->right, right->left);
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(!pRoot) return true;
        return dfs(pRoot, pRoot);
    }

};