Simple py,JAVA code using DFS+recursion,explained in detail!!(Beats 100%)
\n\n# Approach:DFS\n# Intuition\n Describe your first thoughts on how to solve this problem. \n- Lets understand the question first,they are give two trees with
\n\n# Approach:DFS\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Lets understand the question first,they are give two trees with `root1` and `root2`.They asked us if they are *flip equivalent trees.*(A binary tree `X` is flip equivalent to a binary tree `Y` if and only if we can make `X` equal to `Y` after some number of flip operations.)\n- ***Flip equivalent tree:*** A trre is said to be flip equivalent if we get 1 tree from another by swapping `left` and `right` nodes of it\'s child nodes any no of times.(flip operation as follows: choose any node, and swap the `left` and `right` child subtrees.)\n- so what we know is we have `two` options on each node.\n     - Chcek without swapping.\n     - Check with swapping. \n- we will use a *recursive* algorithm to solve this problem.\n- we can tell if both nodes are `None` or `null` they return `True`,this makes sense and this is the one of the `base case` for our recursion.\n- If any one of them is `None` or `null` then they are not equivalent tree,thus we return `False`\n- If `root1.val` is not equal to `root2.val` then we return `False`.\n- The above Forms the *bases cases!!*\n- In the *recursive case* we have `2` options now as stated before.We can check if two trees are equivalent *with and without swapping*.\n- Without swapping is done by `without_swapping` which evaluvates whether the respective `left` and `right` nodes are equivalent.For the current node to be equivalent both `left` `&&` `right` should satisfy.\n- With swapping is done by `with_swapping` which evaluvates whether the  `left1` and `right2` nodes are equivalent also(`&&`) `left2` and `right1` are equivalent.\n- This calls the below recursion function which stops at any one of the base cases,we get a `True` value only if all nodes of subtree\'s recursion passes the base case where all `left` and `right` nodes are null.\n\n```Python3 []\nwithout_swap=self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right)\nwith_swap=self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left)\n```\n```Java []\nboolean without_swap=flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right);\nboolean with_swap=flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left);\n```\n\n- as there are two cases we return ans of any(`||`) recusrion case,if any one recursion cases passes it\'s well and good.\n# Complexity\n- Time complexity:$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python3 []\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:\n        if not root1 and not root2:\n            return True\n        if not root1 or not root2:\n            return False\n        if root1.val!=root2.val:\n            return False\n        without_swap=self.flipEquiv(root1.left,root2.left) and self.flipEquiv(root1.right,root2.right)\n        with_swap=self.flipEquiv(root1.left,root2.right) and self.flipEquiv(root1.right,root2.left)\n        return without_swap or with_swap\n    \n```\n```java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public boolean flipEquiv(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        boolean without_swap=flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right);\n        boolean with_swap=flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left);\n        return without_swap || with_swap;\n        \n    }\n}\n```
['Tree', 'Depth-First Search', 'Recursion', 'Binary Tree', 'Java', 'Python3']