C++ || Shortest Solution Beat 100%✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \n- Two binary trees are flip equivalent if we can transform one into the other by flippi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Two binary trees are flip equivalent if we can transform one into the other by flipping some number of nodes, where flipping means swapping the left and right children of a node.\n- To solve this, we can use recursion to check the values at each node, and for each node, we check both the `"flipped"` and `"non-flipped"` cases to decide if they are equivalent.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- If both nodes are `nullptr`, they are trivially equivalent, so return `true`.\n-  If one node is `nullptr` and the other isn\'t, they can\'t be equivalent, so return `false`.\n- If the values of the two nodes do not match, return `false`.\n- Recursively check both flipped and non-flipped configurations of the children:\n    - Non-flipped: left child with left child and right child with right child.\n    - Flipped: left child with right child and right child with left child.\n- If either configuration is valid, the trees are flip equivalent, so return `true`.\n\n# Complexity\n- Time complexity: `O(n)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(h)` h is the height of the binary tree.\n![Screenshot 2024-10-24 111811.png](https://assets.leetcode.com/users/images/b4f06e84-941e-49d8-b33b-bf6e14b92459_1729748899.0301933.png)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        if(!root1 && !root2) return true;\n        if(!root1 && root2) return false;\n        if(!root2 && root1) return false;\n        if(root1->val != root2->val) return false;\n        if(!flipEquiv(root1->left, root2->right) && !flipEquiv(root1->left, root2->left)) return false;\n        if(!flipEquiv(root1->right, root2->left) && !flipEquiv(root1->right, root2->right)) return false;\n\n        return true;\n    }\n};\n```
['Depth-First Search', 'C++']