LeetCode-951. Flip Equivalent Binary Trees
in leetcode with 0 comment

LeetCode-951. Flip Equivalent Binary Trees

in leetcode with 0 comment

原题链接

题目描述

我们可以为二叉树 T 定义一个翻转操作,如下所示:选择任意节点,然后交换它的左子树和右子树。

只要经过一定次数的翻转操作后,能使 X 等于 Y,我们就称二叉树 X 翻转等价于二叉树 Y。

编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1root2 给出。

示例:

输入:root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
输出:true
解释:We flipped at nodes with values 1, 3, and 5.

解题思路

从跟节点开始 递归判断 两种情况 不需要反转(或者说是反转两次) 或者是需要反转一次

对应的情况:

需要反转 那就是左子树等于左子树 , 右子树等于右子树

不需要反转 那就是左子树等于右子树 , 右子树等于左子树

AC代码

 public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if(root1==null&&root2==null){
            return true;
        }else if( (root1 == null && root2 != null)
                || (root1 != null && root2 == null)){
            return false;
        }
        if(root1.val!=root2.val){
            return false;
        }

        if((flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right)) ||
                (flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left))){
            return true;
        }else{
            return false;
        }
    }