Recursive Solution to Check Flip Equivalent Binary Trees  ||🌟 Beats 100.00% 👏
\n# Intuition\nThe problem is to check if two binary trees are flip equivalent. Two trees are flip equivalent if:\n1. Their roots have the same value.\n2. The l
\n# Intuition\nThe problem is to check if two binary trees are flip equivalent. Two trees are flip equivalent if:\n1. Their roots have the same value.\n2. The left and right subtrees of one tree are either the same as the left and right subtrees of the other tree or flipped.\n\n# Approach\nWe will use recursion to check the two possibilities:\n1. Check if the left subtree of `root1` is equivalent to the left subtree of `root2` and the right subtree of `root1` is equivalent to the right subtree of `root2`.\n2. Alternatively, check if the left subtree of `root1` is equivalent to the right subtree of `root2` and vice versa.\n\n# Complexity\n- **Time complexity:**  \n  $$O(n)$$ \u2014 We traverse each node once.\n  \n- **Space complexity:**  \n  $$O(h)$$ \u2014 This is the maximum depth of recursion, where `h` is the height of the tree.\n\n# Code\n```python\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n        # Base case: if both trees are None, they are equivalent\n        if not root1 and not root2:\n            return True\n        \n        # If one is None and the other is not, or if their root values don\'t match, they can\'t be equivalent\n        if not root1 or not root2 or root1.val != root2.val:\n            return False\n        \n        # Recursively check two possibilities:\n        # 1. Check if left subtree of root1 matches left subtree of root2 \n        #    AND right subtree of root1 matches right subtree of root2.\n        # 2. Check if left subtree of root1 matches right subtree of root2 \n        #    AND right subtree of root1 matches left subtree of root2 (flipped).\n        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \\\n               (self.flipEquiv(root1.right, root2.left) and self.flipEquiv(root1.left, root2.right))\n```\n
['Python3']