Tree

Challenge Given an adjency matrix, find the group of nodes that are connected together. E.g isConnected = [[1,1,0],[1,1,0],[0,0,1]] Will return 2 Data Structure Creating a Disjoin Set data structure using a dictionary. class DisjointSet: def __init__(self, n): self.rank = {i:i for i in range(n)} def __repr__(self): return f"Repr:{self.rank}" def find(self, val): # adding collapsing find original_v = val while self.rank[val] != val: val = self.rank[val] if original_v != val: self.rank[original_v] = val return val def union(self,val1, val2): v1 = self.find(val1) v2 = self.find(val2) self.rank[v2] = v1 Solution class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: ds = DisjointSet(len(isConnected[0])) for n, node in enumerate(isConnected): for j, v in enumerate(node): if v == 1 and j !=n: ds.union(n, j) ct = 0 for k,v in ds.rank.items(): if k == v: ct += 1 return ct

Challenge Given the root of a binary tree, return all duplicate subtrees. You only need to return the root of any of them. Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def __init__(self): self.all_node = [] self.ans = [] self.s = set() def preorder(self, root, arr): arr.append(root.val) if root.left: self.preorder(root.left, arr) else: arr.append(None) if root.right: self.preorder(root.right, arr ) else: arr.append(None) return arr def get_subtree(self, root): res = [self.preorder(root, []), root] current, root = res if current in self.all_node and tuple(current) not in self.s: self.ans.append(root) self.s.add(tuple(current)) else: self.all_node.append(current) def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: queue = [root] while queue: node = queue.pop(0) self.get_subtree(node) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return self.ans Time Complexity: O(n^2) ...

Challenge Given a binary Tree, find the lowest common ancestor of two nodes. Example: LCA(4,9) => 7 LCA() 3 / \ 7 1 / \ \ 4 9 2 Solution 1 - Recursion class Solution: def helper(self, root, nodes): if not root: return None if root in nodes: return root left = self.helper(root.left, nodes) right = self.helper(root.right,nodes) if left and right: return root if left and right is None: return left if right and left is None: return right def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode': return self.helper(root, nodes) Solution 2 - Iterative Another strategy is for each node keep in memory his parent. Then you can go up the ancestry tree and find the lowest they share. ...