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 areflip equivalent. The trees are given by root nodesroot1androot2.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null)
            return true;
        if(root1 == null || root2 == null)
            return false;

        if(root1.val != root2.val)
            return false;

        if(equal(root1.left, root2.left)) {
            if(!equal(root1.right, root2.right))
                return false;
            return flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
        }

        if(equal(root1.left, root2.right)) {
            if(!equal(root1.right, root2.left)) 
                return false;
            return flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
        }

        return false;
    }

    public boolean equal(TreeNode r1, TreeNode r2) {
        if(r1 == null && r2 == null)
            return true;
        if(r1 == null || r2 == null)
            return false;

        return r1.val == r2.val;
    }
}