easy peasy dfs, 0ms runtime, beats 100%  in typescript/java/c++/php/go/python
Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(H)\n\n# Code\ntypescript []\nfunction flipEquiv(node1: TreeNode | null, node2: TreeNode | null): 
# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(H)$$\n\n# Code\n```typescript []\nfunction flipEquiv(node1: TreeNode | null, node2: TreeNode | null): boolean {\n    if (!node1 && !node2) {\n        return true;\n    }\n    else if (node1 && node2) {\n        if (node1.val === node2.val) {\n            if (flipEquiv(node1.left, node2.left) === true && flipEquiv(node1.right, node2.right) === true) {\n                return true;\n            }\n            else if (flipEquiv(node1.left, node2.right) === true && flipEquiv(node1.right, node2.left) === true) {\n                return true;\n            }\n        }\n    }\n    return false;\n};\n```\n```JAVA []\nclass Solution {\n    public boolean flipEquiv(TreeNode node1, TreeNode node2) {\n        if (node1 == null && node2 == null) {\n            return true;\n        } else if (node1 != null && node2 != null) {\n            if (node1.val == node2.val) {\n                if (flipEquiv(node1.left, node2.left) && flipEquiv(node1.right, node2.right)) {\n                    return true;\n                } else if (flipEquiv(node1.left, node2.right) && flipEquiv(node1.right, node2.left)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n}\n```\n```PHP []\nclass Solution {\n    public function flipEquiv($node1, $node2) {\n        if ($node1 === null && $node2 === null) {\n            return true;\n        } elseif ($node1 !== null && $node2 !== null) {\n            if ($node1->val === $node2->val) {\n                if ($this->flipEquiv($node1->left, $node2->left) && $this->flipEquiv($node1->right, $node2->right)) {\n                    return true;\n                } elseif ($this->flipEquiv($node1->left, $node2->right) && $this->flipEquiv($node1->right, $node2->left)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* node1, TreeNode* node2) {\n        if (node1 == nullptr && node2 == nullptr) {\n            return true;\n        } else if (node1 != nullptr && node2 != nullptr) {\n            if (node1->val == node2->val) {\n                if (flipEquiv(node1->left, node2->left) && flipEquiv(node1->right, node2->right)) {\n                    return true;\n                } else if (flipEquiv(node1->left, node2->right) && flipEquiv(node1->right, node2->left)) {\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n};\n```\n```golang []\nfunc flipEquiv(node1 *TreeNode, node2 *TreeNode) bool {\n    if node1 == nil && node2 == nil {\n        return true\n    } else if node1 != nil && node2 != nil {\n        if node1.Val == node2.Val {\n            if flipEquiv(node1.Left, node2.Left) && flipEquiv(node1.Right, node2.Right) {\n                return true\n            } else if flipEquiv(node1.Left, node2.Right) && flipEquiv(node1.Right, node2.Left) {\n                return true\n            }\n        }\n    }\n    return false\n}\n```\n```python []\nclass Solution:\n    def flipEquiv(self, node1, node2):\n        if node1 is None and node2 is None:\n            return True\n        elif node1 is not None and node2 is not None:\n            if node1.val == node2.val:\n                if self.flipEquiv(node1.left, node2.left) and self.flipEquiv(node1.right, node2.right):\n                    return True\n                elif self.flipEquiv(node1.left, node2.right) and self.flipEquiv(node1.right, node2.left):\n                    return True\n        return False\n```\n![typescript.png](https://assets.leetcode.com/users/images/8bc66a88-741c-4c75-9275-c2e429bb57fe_1729731257.1844852.png)\n\n![java.png](https://assets.leetcode.com/users/images/04d62b9e-51ec-449c-894c-1fc5bd09de48_1729731270.6757596.png)\n\n![php.png](https://assets.leetcode.com/users/images/296fd1c9-ca78-4a86-887c-23f85a65cf8b_1729731278.5956361.png)\n\n![c++.png](https://assets.leetcode.com/users/images/07323fae-b98d-4f6b-8b67-370d1d4d5eb1_1729731286.7222137.png)\n\n![2024-10-24_00-33.png](https://assets.leetcode.com/users/images/079839ef-e49b-4eb8-94bd-31d542ff7509_1729730053.612985.png)\n\n![python.png](https://assets.leetcode.com/users/images/fac49c1e-af83-4761-a6db-2e31687d4825_1729731237.8887134.png)\n\n
['Depth-First Search', 'PHP', 'Python', 'C++', 'Java', 'Go', 'TypeScript']