[Java/Python 3] DFS 3 liners and BFS with explanation, time & space: O(n).
Note:\nSome complain the iterative java code and DFS python code are wrong. Thanks for your comment.\n\nIn fact, the codes are correct. The 77th test case is no
# Note:\nSome complain the iterative java code and DFS python code are wrong. Thanks for your comment.\n\nIn fact, **the codes are correct. The 77th test case is not**: \n```\n[1,3,3,4,5,6,null,null,null,7,8]\n[1,3,3,null,6,4,5,null,null,null,null,8,7]\n```\nThere are duplicate values in both trees. However, according to problem description: \n"...\nConstraints:\nEach value in each tree will be a **unique integer** in the range [0, 99]."\nDuplicate values of 3\'s should not appear in either tree. Therefore, this is an invalid test case.\n\n# End of Note.\n\n----\n\n**Recursive version: DFS**\n1. If at least one of the two root nodes is `null`, are they equal? if yes, `true`; if no, `false`;\n2. otherwise, neither node is `null`; if the values of the two nodes are: \n\t2a) NOT equal, return `false`;\n\t2b) equal, compare their children recursively.\n\n```java\n    public boolean flipEquiv(TreeNode r1, TreeNode r2) {\n        if (r1 == null || r2 == null) return r1 == r2;\n        return r1.val == r2.val &&\n               (flipEquiv(r1.left, r2.left) && flipEquiv(r1.right, r2.right) || \n               flipEquiv(r1.left, r2.right) && flipEquiv(r1.right, r2.left));\n    }\n```\n```python\n    def flipEquiv(self, r1: TreeNode, r2: TreeNode) -> bool:\n        if not r1 or not r2: return r1 == r2 == None\n        return r1.val == r2.val and (self.flipEquiv(r1.left, r2.left) and  self.flipEquiv(r1.right, r2.right) \\\n                                or self.flipEquiv(r1.left, r2.right) and self.flipEquiv(r1.right, r2.left))\n```\n\n----\n**Iterative version: BFS**\n```java\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        Queue<TreeNode> q1 = new LinkedList<>(), q2 = new LinkedList<>();\n        q1.offer(root1);\n        q2.offer(root2);\n        while (!q1.isEmpty() && !q2.isEmpty()) {\n            TreeNode n1 = q1.poll(), n2 = q2.poll();\n            if (n1 == null || n2 == null) {\n                if (n1 != n2) return false;\n                else continue;\n            }\n            if (n1.val != n2.val) {\n                return false;\n            }\n            if (n1.left == n2.left || n1.left != null && n2.left != null && n1.left.val == n2.left.val) {\n                q1.addAll(Arrays.asList(n1.left, n1.right));\n            }else {\n                q1.addAll(Arrays.asList(n1.right, n1.left));\n            }\n            q2.addAll(Arrays.asList(n2.left, n2.right));\n        }\n        return q1.isEmpty() && q2.isEmpty();\n    }\n```\n```python\n    def flipEquiv(self, r1: TreeNode, r2: TreeNode) -> bool:\n        dq1, dq2 = map(collections.deque, ([r1], [r2]))\n        while dq1 and dq2:\n            node1, node2 = dq1.popleft(), dq2.popleft()\n            if node1 == node2 == None: continue \n            elif not node1 or not node2 or node1.val != node2.val: return False\n\n            if node1.left == node2.left == None or node1.left and node2.left and node1.left.val ==  node2.left.val:\n                dq1.extend([node1.left, node1.right])\n            else:\n                dq1.extend([node1.right, node1.left])\n            dq2.extend([node2.left, node2.right])\n        return not dq1 and not dq2\n```\n**Iterative version: DFS**\n```java\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        Stack<TreeNode> stk1 = new Stack<>(), stk2 = new Stack<>();\n        stk1.push(root1);\n        stk2.push(root2);\n        while (!stk1.isEmpty() && !stk2.isEmpty()) {\n            TreeNode n1 = stk1.pop(), n2 = stk2.pop();\n            if (n1 == null && n2 == null) {\n                continue;\n            }else if (n1 == null || n2 == null || n1.val != n2.val) {\n                return false;\n            }\n\n            if (n1.left == n2.left || n1.left != null && n2.left != null && n1.left.val == n2.left.val) {\n                stk1.addAll(Arrays.asList(n1.left, n1.right));\n            }else {\n                stk1.addAll(Arrays.asList(n1.right, n1.left));\n            }\n            stk2.addAll(Arrays.asList(n2.left, n2.right));\n        }\n        return stk1.isEmpty() && stk2.isEmpty();\n    }\n```\n\n```python\n    def flipEquiv(self, r1: TreeNode, r2: TreeNode) -> bool:\n        stk1, stk2 = [r1], [r2]\n        while stk1 and stk2:\n            node1, node2 = stk1.pop(), stk2.pop()\n            if node1 == node2 == None: continue \n            elif not node1 or not node2 or node1.val != node2.val: return False\n            \n            if node1.left == node2.left == None or node1.left and node2.left and node1.left.val == node2.left.val:\n                stk1.extend([node1.left, node1.right])\n            else:\n                stk1.extend([node1.right, node1.left])\n            stk2.extend([node2.left, node2.right])\n        return not stk1 and not stk2\n```\n\n----\n**Update:** \nFor some time, I forgot the following constraint and changed the comlexity from O(n) to O(n ^ 2):\n`Each value in each tree will be a unique integer in the range [0, 99]`\n\nThe follows are correct **only without the above condition**.\n=============================\nComplexity analysis corrected from `O(n)` to `O(n ^ 2)`.\n**Analysis:**\n\nIn worst case, the recursion corresponds to a perfect quaternary (means `4`-nary) tree, which has `4 ^ d = N ^ 2` nodes, and we have to traverse all nodes. `d = logN` is the depth of the binary tree.\n\nOne worst case for input:\ntwo perfect binary trees: root1 & root2. \n1. Root1\'s nodes are all `0`s; \n2. Root2\'s nodes are all `0`s, with the exception that left and right bottoms are both `1`s.\n\n**Time & Space: O(n ^ 2).**\nThanks correction from **@heruslu @coder_coder @Everestsky007**\n\n----\nQ & A:\n\nQ1:\nwhy it\'s N^2 and how it corresponds to a 4-nary tree? why it was initially considered O(N)?\nA1:\nYes, because the return statement has 4 recursive calls.\n\nThe problem states `Each value in each tree will be a unique integer in the range [0, 99]`, hence we have the following deduction:\n```\nir1.left.val == r2.left.val and r1.left.val == r2.right.val, \n\nat most 1 of the 2 relations is true; otherwise r2.left.val == r2.right.val, this contradicts the above problem constraint.\n```\n Therefore, at least 1 out of flipEquiv(r1.left, r2.left) and flipEquiv(r1.left, r2.right) will terminate; Similiarly,  at least 1 out of flipEquiv(r1.right, r2.right) andflipEquiv(r1.right, r2.leftt) will terminate. \n\nObviously at most 2 out of the 4 recursive calls could go all the way down to the bottom.\n\nThat is why the time is O(N).\n\nWithout the aforementioned constraint, all of the 4 recursive calls could expand the 4-nary tree to the bottom and result time O(N ^ 2).\n\n----\n\nQ2: In iterative Python code, why there needs to be a comparison of `node1.left == node2.left`?\nA2: It is a short form of `node1.left == node2.left == None`.
[]