Lowest Common Ancestors
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. ...