Easy DFS->1 liner vs BFS||beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nEasy dfs.\n5 solutions, 2 1-line C++, 1 1-line Python\nDFS implemations are easy. So ma
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nEasy dfs.\n5 solutions, 2 1-line C++, 1 1-line Python\nDFS implemations are easy. So make a BFS solution.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse recursive DFS. The statement `root1==root2` is same as `!root1 && !root2`.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n# Code||0ms beats 100%\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 1;\n        if (!root1 || !root2 || root1->val != root2->val) return 0;\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# C++ 1-liner using ternary operator||0ms beats 100%\n```\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        return (root1 == root2)?1:\n        (!root1 || !root2 || root1->val != root2->val)?0:\n        (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# C++ 1-liner same as the one of @Sergei||0ms beats 100%\n```\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        return (root1 == root2)||\n        (root1 && root2 && root1->val==root2->val &&\n        ((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# Python 1-liner||0ms  beats 100%\n```\nclass Solution:\n    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n        return root1==root2 or (root1!=None and root2!=None and root1.val == root2.val and ((self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))))\n      \n```\n# BFS ||0ms beats 100%\n```\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    using info = pair<TreeNode*, TreeNode*>;// info pair\n\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        if (root1 == root2) return 1;       \n        if (!root1 || !root2 || root1->val != root2->val) return 0;\n\n        queue<info> q;\n        q.emplace(root1, root2);\n\n        while (!q.empty()) {\n            auto [node1, node2] = q.front();\n            q.pop();\n            //    cout<<((node1)?node1->val:-1)<<","<<((node2)?node2->val:-1)<<endl;\n            if (node1 == node2) continue;\n            if (!node1 || !node2 || node1->val != node2->val) return 0;\n\n            // Get the left and right children of both nodes\n            auto L1 = node1->left, L2 = node2->left;\n            auto R1 = node1->right, R2 = node2->right;\n\n            // check  non-flipped (L1 with L2 and R1 with R2)\n            if (((!L1 && !L2) || (L1 && L2 && L1->val == L2->val)) &&\n                ((!R1 && !R2) || (R1 && R2 && R1->val == R2->val))) \n            {\n                q.emplace(L1, L2);\n                q.emplace(R1, R2);\n            }\n            // Then, check flipped  (L1 with R2 and R1 with L2)\n            else if (((!L1 && !R2) || (L1 && R2 && L1->val == R2->val)) &&\n                     ((!R1 && !L2) || (R1 && L2 && R1->val == L2->val)))\n            {\n                q.emplace(L1, R2);\n                q.emplace(R1, L2);\n            } \n            else return 0;\n        }\n        return 1; \n    }\n};\n```
['Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'C++', 'Python3']