Skip to content

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
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {
    unordered_set<TreeNode*> nodesSet{nodes.begin(), nodes.end()};
    return lca(root, nodesSet);
  }

 private:
  TreeNode* lca(TreeNode* root, unordered_set<TreeNode*>& nodesSet) {
    if (root == nullptr)
      return nullptr;
    if (nodesSet.count(root))
      return root;
    TreeNode* left = lca(root->left, nodesSet);
    TreeNode* right = lca(root->right, nodesSet);
    if (left != nullptr && right != nullptr)
      return root;
    return left == nullptr ? right : left;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
    Set<TreeNode> nodesSet = new HashSet<>(Arrays.asList(nodes));
    return lca(root, nodesSet);
  }

  private TreeNode lca(TreeNode root, Set<TreeNode> nodesSet) {
    if (root == null)
      return null;
    if (nodesSet.contains(root))
      return root;
    TreeNode left = lca(root.left, nodesSet);
    TreeNode right = lca(root.right, nodesSet);
    if (left != null && right != null)
      return root;
    return left == null ? right : left;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
      left = lca(root.left)
      right = lca(root.right)
      if left and right:
        return root
      return left or right

    return lca(root)