C++ Solution || Simple DFS || Beats 100%
Intuition\nThe problem asks whether two binary trees are flip equivalent. Two trees are flip equivalent if they are the same when flipped at any node, meaning t
# Intuition\nThe problem asks whether two binary trees are flip equivalent. Two trees are flip equivalent if they are the same when flipped at any node, meaning that at any node, we can swap the left and right subtrees.\n\nMy first thought is that we need to check the values of the nodes in a recursive manner. At each node, we either check if both left and right subtrees are the same without flipping, or we check if they are the same with flipping (i.e., left subtree of one tree corresponds to the right subtree of the other and vice versa).\n\n# Approach\nWe can solve this using recursion. At each step:\n\n1. If both nodes are `NULL`, they are trivially equivalent.\n2. If only one of them is `NULL` or their values are different, they cannot be flip equivalent.\n3. Recursively check the following two possibilities:\n    - The left subtree of the first tree is flip equivalent to the left subtree of the second tree, and the right subtree of the first tree is flip equivalent to the right subtree of the second tree.\n    - The left subtree of the first tree is flip equivalent to the right subtree of the second tree, and the right subtree of the first tree is flip equivalent to the left subtree of the second tree.\n\nBy considering both cases, we ensure that we account for potential flips at every node.\n\n# Complexity\n- Time complexity: $$O(n)$$ \n\n- Space complexity: $$O(h)$$\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),\n * right(right) {}\n * };\n */\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        if (root1 == NULL || root2 == NULL)\n            return root1 == root2;\n        if (root1->val != root2->val)\n            return false;\n        return (flipEquiv(root1->left, root2->left) &&\n                flipEquiv(root1->right, root2->right)) ||\n                flipEquiv(root1->left, root2->right) &&\n                flipEquiv(root1->right, root2->left);\n    }\n};\n```\n# *Quote of the Day*\n> ***Deep recursion in trees is like exploring the depths of thought \u2014 the deeper you go, the more complex and beautiful the journey.***\n\n![1721315779911.jpeg](https://assets.leetcode.com/users/images/2db5fad5-188b-4d5e-97ab-b6cae4882922_1729734739.1505587.jpeg)\n\n
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']