951. Flip Equivalent Binary Trees


For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.

Example 1:

Input: 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] Output: true Explanation: We flipped at nodes with values 1, 3, and 5. Flipped Trees Diagram


Each tree will have at most 100 nodes. Each value in each tree will be a unique integer in the range [0, 99].




class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if(root1==null && root2==null) return true;
        if(root1 != null && root2 !=null && root1.val == root2.val){
            return flipEquivHelper(root1,root2);
        }else return false;
    public static boolean flipEquivHelper(TreeNode root1,TreeNode root2){
        int left1 = root1.left==null?-1:root1.left.val;
        int right1 = root1.right==null?-1:root1.right.val;
        int left2 = root2.left==null?-1:root2.left.val;
        int right2 = root2.right==null?-1:root2.right.val;
        if(left1==left2 && right1 == right2 ){
            boolean left = false;
            if(left1!=-1) left = flipEquivHelper(root1.left,root2.left);
            else left=true;
            boolean right = false;
            if(right1!=-1) right = flipEquivHelper(root1.right,root2.right);
            else right = true;
            return left&right;
        }else if(left1==right2 && right1==left2){
            boolean left = false;
            if(left1!=-1) left = flipEquivHelper(root1.left,root2.right);
            else left = true;
            boolean right = false;
            if(right1!=-1) right = flipEquivHelper(root1.right,root2.left);
            else right = true;
            return  left&right;
        }else return false;