Beats 100% || C++ || DFS || Intuitive
Intuition\n Describe your first thoughts on how to solve this problem. \nAt each node, there can be only two cases\n1. Subtrees of that node are swapped\n2. Sub
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAt each node, there can be only two cases\n1. Subtrees of that node are swapped\n2. Subtrees of that node are not swapped\n\nSo at each node we have to check for these two cases only, if any of the case is true, then that node is flip equivalent.\nWe will use dfs to check for every node recursively\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIf root1 and root2 are null, it is flip equivalent, so return true\nIf anyone of the root is null and other is not null, or if both roots have different values, then they are not flip equivalent, so return false\n\nfor swap case check for root1->left == root2->right and root1->right == root2->left, recursively\nfor non swap case check for root1->left == root2->left and root1->right == root2->right, recursively\nIf any of the recursive call(swap or non-swap) returns true, then the that node is flip equivalent, and 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(n)$$\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 {\nprivate:\n    bool dfs(TreeNode* root1, TreeNode* root2){\n        if(!root1 && !root2) return true;\n        else if(!root1 || !root2 || (root1->val!=root2->val)) return false;\n\n        return\n            dfs(root1->left,root2->right) && dfs(root1->right,root2->left) // swap case\n        ||  dfs(root1->left,root2->left) && dfs(root1->right,root2->right); // no swap case\n    }\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        return dfs(root1, root2);\n    }\n};\nauto speedup = [](){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']