Beats 100% Python3 🚀🚀🚀 | Simple DFS 💫💫💫
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves determining whether two binary trees are flip equivalent. Flip equ
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves determining whether two binary trees are flip equivalent. Flip equivalence means that by flipping some nodes (swapping left and right subtrees), you can transform one tree into the other. The key observation is that either:\n\n1. 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, you can flip the subtrees, so the left subtree of root1 is equivalent to the right subtree of root2, and vice versa.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Base case:\n    - If both trees are None, they are trivially equivalent.\n    - If one tree is None and the other is not, they cannot be equivalent.\n    - If the values of root1 and root2 are different, they cannot be equivalent.\n2. Recursive check:\n    - Recursively check the flip equivalence of the left and right subtrees in both scenarios:\n        - Either the left subtrees are equivalent and the right subtrees are equivalent.\n        - Or, the left subtree of one tree is equivalent to the right subtree of the other, and vice versa.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\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        if not root1:\n            return not root2\n        if not root2:\n            return not root1\n        if root1.val != root2.val:\n            return False\n        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'Python3']