Flip That Tree: Same Roots, Different Looks? (Using recursion, Daily Question 24/10/24).
Intuition\n Describe your first thoughts on how to solve this problem. \nAs we are only swapping the nodes of a parent, the children of every ndoe in the both t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs we are only swapping the nodes of a parent, the children of every ndoe in the both trees will be same. If not return false.\n\nThe first thought is to do DFS. By doing DFS store the children of a node. The node val(Integer) will be key and the value will the the children(List of integers). Sort every value. \n\n# Approach\nStep1: Do DFS for root 2 and store children in a hashmap.\nStep2: For root1, check if the children of every node is same.\nStep3: If not return false.\nStep4: Do the same for root1.left and root1.right using recursion. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n1 + n2) where n1= number of nodes in root1 and n2= number of nodes in root2.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n2 + h1 + h2) where n2= size of hashmap, h1= height of root1, h2= height of root2.\n\n# Code\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 void children(TreeNode root, HashMap<Integer, List<Integer>> l){\n        if(root==null) return;\n        if(!l.containsKey(root.val)) {\n            List<Integer> l1= new ArrayList<>();\n            if(root.left!=null) l1.add(root.left.val);\n            if(root.right!=null) l1.add(root.right.val);\n            Collections.sort(l1);\n            l.put(root.val, l1);\n        }\n        children(root.left, l);\n        children(root.right, l);\n    }\n    public boolean check(TreeNode root, HashMap<Integer, List<Integer>> l){\n        if(root==null) return true;\n        List<Integer> x= new ArrayList<>();\n        if(root.left!=null)x.add(root.left.val);\n        if(root.right!=null) x.add(root.right.val);\n        Collections.sort(x);\n        if(!l.get(root.val).equals(x)) return false;\n        boolean left= check(root.left, l);\n        boolean right= check(root.right, l);\n        return left && right;\n    }\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        if(root1==null && root2==null) return true;\n        if(root1==null || root2==null) return false;\n        if(root1.val!=root2.val) return false;\n        HashMap<Integer, List<Integer>> hm= new HashMap<>();\n        children(root2, hm);\n        return check(root1, hm);\n    }\n}\n```
['Java']