# 1676. Lowest Common Ancestor of a Binary Tree IV

• Time: $O(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 class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, vector& nodes) { unordered_set nodesSet{begin(nodes), end(nodes)}; return lca(root, nodesSet); } private: TreeNode* lca(TreeNode* root, unordered_set& nodesSet) { if (root == nullptr) return nullptr; if (nodesSet.count(root)) return root; TreeNode* l = lca(root->left, nodesSet); TreeNode* r = lca(root->right, nodesSet); if (l && r) return root; return l ? l : r; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) { Set nodesSet = new HashSet<>(Arrays.asList(nodes)); return lca(root, nodesSet); } private TreeNode lca(TreeNode root, Set nodesSet) { if (root == null) return null; if (nodesSet.contains(root)) return root; TreeNode l = lca(root.left, nodesSet); TreeNode r = lca(root.right, nodesSet); if (l != null && r != null) return root; return l == null ? r : l; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode': nodes = set(nodes) def lca(root: 'TreeNode') -> 'TreeNode': if not root: return None if root in nodes: return root l = lca(root.left) r = lca(root.right) if l and r: return root return l or r return lca(root)