Python | DFS
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -
[see the Successfully Accepted Submission](https://leetcode.com/problems/flip-equivalent-binary-trees/submissions/1431956481/?envType=daily-question&envId=2024-10-24)\n\n# Code\n```python3 []\nclass Solution:\n    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n        # Base cases\n        if not root1 and not root2:  # Both are None\n            return True\n        if not root1 or not root2:  # One is None and the other is not\n            return False\n        if root1.val != root2.val:  # Values are not equal\n            return False\n        \n        # Check if the trees are flip equivalent\n        no_flip = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)\n        flip = self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)\n        \n        return no_flip or flip\n```\n\n## Approach\n\nWe can use a recursive approach to solve this problem. Here\'s the breakdown:\n\n### Base Case:\n- If both trees are empty (`root1` and `root2` are both `None`), then they are trivially flip equivalent. Return `True`.\n- If one tree is empty and the other is not, they cannot be equivalent, so return `False`.\n- If the values at `root1` and `root2` are different, return `False` because the trees are not equivalent if the roots have different values.\n\n### Recursive Case:\nWe need to check two possible scenarios:\n1. **No flip**: Compare the left subtree of `root1` with the left subtree of `root2` and the right subtree of `root1` with the right subtree of `root2`. If both match, we return `True`.\n2. **Flip**: Compare the left subtree of `root1` with the right subtree of `root2` and the right subtree of `root1` with the left subtree of `root2`. If both match after flipping, we return `True`.\n\nIf either of the above cases holds, the trees are flip equivalent.\n\n---\n\n## Explanation of the Code:\n\n### Base Cases:\n- If both `root1` and `root2` are `None`, they are flip equivalent, so return `True`.\n- If one is `None` and the other is not, return `False`.\n- If the values at `root1` and `root2` are different, return `False`.\n\n### Recursive Cases:\nThe function recursively checks two scenarios:\n1. **No flip**: The left subtree of `root1` is compared with the left subtree of `root2`, and the right subtree of `root1` is compared with the right subtree of `root2`.\n2. **Flip**: The left subtree of `root1` is compared with the right subtree of `root2`, and the right subtree of `root1` is compared with the left subtree of `root2`.\n\nIf either scenario returns `True`, the trees are flip equivalent.\n\n---\n\n## Time Complexity:\nEach node in the trees is visited once, and each comparison takes constant time. Thus, the time complexity is **O(n)**, where `n` is the number of nodes in the trees.\n\n## Space Complexity:\nThe space complexity is determined by the recursion depth, which is proportional to the height of the tree. In the worst case, the space complexity is **O(h)**, where `h` is the height of the tree. For a balanced tree, `h` is **O(log n)**, and for a skewed tree, it is **O(n)**.\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']