Java O(n) recursive solution
First we check the case that the root may be null or the roots\' values are not equal. Then we check recursively.\n\nSince each node has a unique value, we can 
First we check the case that the root may be null or the roots\' values are not equal. Then we check recursively.\n\nSince each node has a unique value, we can tell that either (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) is valid, or (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left) is valid. But they can not be valid at the same time. Thus each flipEquiv will split into two new recursive functions, and the maximum height is Min(height(root1), height(root2)). Thus the time complexity is 2 ^ (Min(height(root1), height(root2))) = Min(n_root1, n_root2), where n_root1 is the number of nodes in tree1 and n_root2 is the number of nodes in tree2.\n``` \nclass Solution {\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        if (root1 == null) return root2 == null;\n        if (root2 == null) return root1 == null;\n        if (root1.val != root2.val) return false;\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```
[]