💡 | O(n) | C++, Java, Python 0ms Beats 100% | DFS for Flip Equivalent Binary Trees
\n\n---\n\n> # Intuition\nThe problem asks whether two binary trees can be made equivalent by flipping any number of nodes, swapping the left and right child su
#\n\n---\n\n> # Intuition\nThe problem asks whether two binary trees can be made equivalent by flipping any number of nodes, swapping the left and right child subtrees. This can be solved using **Depth First Search (DFS)** by recursively comparing nodes in both trees. At each step, either the left and right subtrees must match directly, or we can check if flipping them makes them match.\n\n> # Approach\nThe core idea is to traverse both trees simultaneously, comparing nodes. If both are **null**, they are trivially equivalent; if one is **null** and the other isn\'t, or their values differ, the trees are not equivalent. If the values match, we recursively check two cases: without flipping (compare left subtrees and right subtrees of both trees) and with flipping (compare the left subtree of one tree with the right subtree of the other, and vice versa). If either condition holds, the trees are flip equivalent.\n\n> # Complexity\n- **Time Complexity** $$O(n)$$, where $$n$$ is the number of nodes in the trees. We visit each node once.\n- **Space Complexity** $$O(h)$$, where $$h$$ is the height of the trees due to the recursive call stack.\n\n---\n> # Code\n```cpp []\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* r1, TreeNode* r2) {\n        return !r1 && !r2 || r1 && r2 && r1->val == r2->val &&\n               ((flipEquiv(r1->left, r2->left) && flipEquiv(r1->right, r2->right)) ||\n                (flipEquiv(r1->right, r2->left) && flipEquiv(r1->left, r2->right)));\n    }\n};\n```\n```python3 []\nclass Solution:\n    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n        if not root1 and not root2:\n            return True\n        if not root1 or not root2 or root1.val != root2.val:\n            return False\n        return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \\\n               (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))\n```\n```java []\nclass Solution {\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        if (root1 == null && root2 == null) return true;\n        if (root1 == null || root2 == null || root1.val != root2.val) return false;\n        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||\n               (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));\n    }\n}\n```\n---\n\n> **CPP**\n> ![image.png](https://assets.leetcode.com/users/images/61693d91-5bb8-4fed-8175-c98eeb3963d5_1729758637.9297006.png)\n> **Java**\n> ![image.png](https://assets.leetcode.com/users/images/fa062ac9-0bd3-425b-bc36-369c6efa77ab_1729758663.9204538.png)\n![image.png](https://assets.leetcode.com/users/images/910e9df5-4bd7-4368-b4ce-b4c531289eb3_1729758651.271653.png)\n> **Python3**\n> ![Designer.png](https://assets.leetcode.com/users/images/5395952a-4267-4b87-b81f-f28780669704_1726803172.327018.png)\n\n---\n> ### Additional Note\n> This DFS approach efficiently handles the comparison of both trees in all possible configurations, ensuring that flip equivalence is checked thoroughly.\n\n---\n\n---
['C++', 'Java', 'Python3']