✅Easy and Clean Code (C++ / Java) Beats 100 % ✅
\n### # Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about checking whether two binary trees are flip equivalent. A t
\n### # Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about checking whether two binary trees are flip equivalent. A tree can be made equivalent to another by either keeping the left and right children as they are, or by flipping them. This means that at each node, we should check if the current subtrees are already equivalent or if they can be made equivalent by swapping the left and right children. This recursive process can be applied at each node until all nodes are processed.\n\n### # Approach\n<!-- Describe your approach to solving the problem. -->\n1. Start by checking the base cases:\n   - If both nodes are `null`, they are equivalent.\n   - If one node is `null` and the other is not, they cannot be equivalent.\n   - If the values of the nodes do not match, they are not equivalent.\n   \n2. Recursively check both possible configurations at each node:\n   - Without flipping: Check if the left subtree of `root1` is equivalent to the left subtree of `root2`, and the right subtree of `root1` is equivalent to the right subtree of `root2`.\n   - With flipping: Check if the left subtree of `root1` is equivalent to the right subtree of `root2`, and the right subtree of `root1` is equivalent to the left subtree of `root2`.\n\n3. If either of the two configurations (without flipping or with flipping) is valid, the trees are flip equivalent.\n\n### # Complexity\n- **Time complexity**:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity is \\( O(n) \\), where \\( n \\) is the number of nodes in the trees. This is because we need to visit each node once in both trees to compare them recursively.\n\n- **Space complexity**:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is \\( O(h) \\), where \\( h \\) is the height of the tree. This comes from the recursion stack depth, which can go up to the height of the tree in the worst case. For a balanced tree, this would be \\( O(\\log n) \\), but for an unbalanced tree, it could be \\( O(n) \\).\n# Code\n```Cpp []\nclass Solution {\n    bool isFlip(TreeNode* root1, TreeNode* root2) {\n        if(root1 == nullptr && root2 == nullptr) return true;\n        \n        if((root1 != nullptr && root2 == nullptr) || (root1 == nullptr && root2 != nullptr)) return false;\n\n        if (root1->val != root2->val) return false;\n\n        return (isFlip(root1->left, root2->left) && isFlip(root1->right, root2->right)) ||\n               (isFlip(root1->left, root2->right) && isFlip(root1->right, root2->left));\n    }\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        if(root1 == nullptr && root2 == nullptr) {\n            return true;\n        }\n\n        return isFlip(root1, root2);\n    }\n};\n```\n```java []\nclass Solution {\n    private boolean isFlip(TreeNode root1, TreeNode root2) {\n        if (root1 == null && root2 == null) {\n            return true;\n        }\n        if (root1 == null || root2 == null) {\n            return false;\n        }\n        if (root1.val != root2.val) {\n            return false;\n        }\n        return (isFlip(root1.left, root2.left) && isFlip(root1.right, root2.right)) ||\n               (isFlip(root1.left, root2.right) && isFlip(root1.right, root2.left));\n    }\n\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        return isFlip(root1, root2);\n    }\n}\n\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java']