Python | 99% Speed | One Liner
Python | 99% Speed | One Liner\n\nA) Pre-Sorting Children Nodes\n\nSince all nodes have unique values, we can always pre-sort the children of any pair of "root"
**Python | 99% Speed | One Liner**\n\n**A) Pre-Sorting Children Nodes**\n\nSince all nodes have unique values, we can always pre-sort the children of any pair of "root"nodes to make sure that we\'re traversing the Binary Tree in the best possible way. The code below presents an easy implementation:\n\n```\nclass Solution:\n    def flipEquiv(self, root1, root2):\n        fsort = lambda n: sorted( [n.left,n.right], key = lambda x: (x.val if x else -1) )\n        def dfs(n1,n2):\n            if n1 and n2:\n                if n1.val!=n2.val:\n                    return False\n                return all([ dfs(a,b) for a,b in zip(fsort(n1),fsort(n2)) ])\n            # Note:\n            #     - Either n1 or n2 are Null at this point, so...\n            #         - If one is a TreeNode, there\'s a mismatch.\n            #         - If both are Null, everything is ok\n            return False if (n1 or n2) else True\n        return dfs(root1,root2)\n```\n\n\n**B) Double Testing**\n\nWhile the Solution (A) works with high efficiency (since sorting is a local O(1) step), we can also take a simpler approach, which is attempting to traverse the Binary Trees in the two possible ways (left==left or left==right across roots). This works because nodes have unique values, so one of the 2 possibilities will take an immediate exit, leaving us with a time complexity of O(n). The execution speed of this code should be similar to Solution (A). For some reason, LeetCode rated it as faster (probably because we perform less O(1) operations).\n\n```\nclass Solution:\n    def flipEquiv(self, n1, n2):\n        if n1 and n2:\n            if n1.val!=n2.val:\n                return False\n            matches = self.flipEquiv\n            return ( matches(n1.left,n2.left ) and matches(n1.right,n2.right) ) or \\\n                   ( matches(n1.left,n2.right) and matches(n1.right,n2.left ) )\n        return False if (n1 or n2) else True\n```\n\n**C) One Liner**\n\nThis solution is a crazy one-liner, which compresses the logic of Solution (B) into a single expression. It\'s just a curiosity :)\n\n```\nclass Solution:\n    def flipEquiv(self, n1, n2):\n        return ( False if (n1.val!=n2.val) else ((self.flipEquiv(n1.left,n2.left ) and self.flipEquiv(n1.right,n2.right)) or (self.flipEquiv(n1.left,n2.right) and self.flipEquiv(n1.right,n2.left ))) ) if (n1 and n2) else ( False if (n1 or n2) else True )\n```
['Python', 'Python3']