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&nbsp;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.

Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

&nbsp;
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.


Example 2:

Input: root1 = [], root2 = []
Output: true


Example 3:

Input: root1 = [], root2 = [1]
Output: false


&nbsp;
Constraints:


	The number of nodes in each tree is in the range [0, 100].
	Each tree will have unique node values in the range [0, 99].


class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def swap(root):
            if root.right is None or (root.left is not None and root.left.val > root.right.val):
                root.left, root.right = root.right, root.left
        
        def equal(root1, root2):
            if root1 is None or root2 is None:
                return root1 is None and root2 is None
            
            swap(root1)
            swap(root2)
            
            return (root1.val == root2.val and
                    equal(root1.left, root2.left) and
                    equal(root1.right, root2.right))
        
        return equal(root1, root2)
class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        return helper(root1, root2);
    }
    
    private boolean helper(TreeNode x, TreeNode y)
    {
        if(x == null && y == null) return true;
        if(x == null || y == null || x.val != y.val) return false;
        boolean similarity = helper(x.left, y.left) && helper(x.right, y.right); // check if 2 subtrees are similar
        boolean swap = helper(x.left, y.right) && helper(x.right, y.left); // check if the 2 subtrees can be similar after swapping the left & right subtrees with each other
        
        return similarity || swap; // if either true, means we can flip to match both trees
    }
}
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL && root2 == NULL)
            return true;
        else if (root1 == NULL || root2 == NULL)
            return false;
        else if (root1 -> val != root2 -> val)
            return false;

        return (flipEquiv(root1 -> left, root2 -> right) && flipEquiv(root1 -> right, root2 -> left)) || (flipEquiv(root1 -> left, root2 -> left) && flipEquiv(root1 -> right, root2 -> right));
    }
};
var flipEquiv = function(root1, root2) {
    const flipEquivHelper = (r1 = root1, r2 = root2) => {
        if(!r1 && !r2) return true;
        
        if(!r1 || !r2) return false;
        
        if(r1.val != r2.val) return false;
        
        let ans = false;
        // normal
        ans = ans || (
            flipEquivHelper(r1.left, r2.left) && 
            flipEquivHelper(r1.right, r2.right)
        );
        // flip
        ans = ans || (
            flipEquivHelper(r1.right, r2.left) && 
            flipEquivHelper(r1.left, r2.right)
        );
        return ans;
    }
    return flipEquivHelper();
};
Flip Equivalent Binary Trees