Day101 | 灵神 | 二叉树 翻转等价二叉树

951.翻转等价二叉树

951. 翻转等价二叉树 - 力扣（LeetCode）

思路：

一开始笔者的思路就是判断完当前结点相不相等以后再去判断左右子树相不相等，不相等的话用swap翻转之后再次比较，这样太麻烦了，而且写的时候难免出错

笔者就去评论区找大佬了

大佬的思路是：反正是有限次数的翻转，那么只会有两种情况

情况1：不需要翻转，也就是root1的左子树和root2的左子树相同，右子树和右子树相同

情况2：需要翻转，也就是没有翻转之前root1的左子树和root2的右子树相同，root1的右子树和root2的左子树相同

那我还翻转什么了，直接把这两种情况都递归一下，第一次比较左左和右右，第二次比较左右和右左，只要有一次可以比较成功那就是可以翻转，根本不用什么swap

完整代码：

笔者代码：觉得看着复杂可以看下面的等价代码

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

等价版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        auto dfs = [&](auto&& dfs, TreeNode* p, TreeNode* q) {
            if (!p || !q)
                return p == q;

            if (p->val != q->val)
                return false;

            bool l1ans = dfs(dfs, p->left, q->left);
            bool l2ans = dfs(dfs, p->left, q->right);
            bool r1ans = dfs(dfs, p->right, q->left);
            bool r2ans = dfs(dfs, p->right, q->right);

            return (l1ans && r2ans) || (l2ans && r1ans);
        };

        return dfs(dfs, root1, root2);
    }
};