Lowest Common Ancestor of a Binary Tree IV

You can solve this problem by performing a Depth First Search (DFS) through the tree and checking if the nodes are in the provided list. Below is a step-by-step solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
        nodes_set = set(nodes)

        def dfs(node):
            if not node:
                return None

            # If the current node is in the nodes list, return the node
            if node in nodes_set:
                return node

            # Recur on the left and right children
            left_lca = dfs(node.left)
            right_lca = dfs(node.right)

            # If both left and right children have nodes, then current node is the LCA
            if left_lca and right_lca:
                return node

            # Otherwise, return the child that contains the node(s)
            return left_lca if left_lca else right_lca

        return dfs(root)

Explanation

  1. Convert the list of nodes to a set for quick lookup.
  2. Create a recursive function dfs that takes a node as input.
  3. If the current node is in the nodes set, return the node as it’s part of the LCA.
  4. Recursively call dfs on the left and right children of the current node.
  5. If both left and right children return non-null values, then the current node is the lowest common ancestor of those nodes, so return it.
  6. Otherwise, return the non-null child that contains the node(s), or null if neither child contains a node.
  7. Call dfs starting from the root and return the result, which will be the LCA of all the nodes in nodes.