Duplicate subtree in Binary Tree
Given a binary tree, find out whether it contains a duplicate sub-tree of size two or more, or not.
- Time : O(n * n)
- Space : O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Solution { Map<Integer, List<Node>> mp = new HashMap<>(); void travel(Node node) { if(node == null) return; if(node.left != null || node.right != null) { List<Node> list = mp.getOrDefault(node.data, new ArrayList<>()); list.add(node); mp.put(node.data, list); travel(node.left); travel(node.right); } } boolean equal(Node a, Node b) { if(a == null || b == null) return a == null && b == null; return a.data == b.data && equal(a.left, b.left) && equal(a.right, b.right); } int dupSub(Node root) { mp.clear(); travel(root); for(List<Node> nodes : mp.values()) { int n = nodes.size(); for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(equal(nodes.get(i), nodes.get(j))) return 1; } } }
return 0; } }
|