Medium

Lowest Common Ancestor of a Binary Tree IV

LAB

Given directed tree edges [parent, child], a root value, and target node values, return the value of their lowest common ancestor.

EXAMPLES

Example 1

Input
{
  "edges": [
    [
      3,
      5
    ],
    [
      3,
      1
    ],
    [
      5,
      6
    ],
    [
      5,
      2
    ],
    [
      1,
      0
    ],
    [
      1,
      8
    ],
    [
      2,
      7
    ],
    [
      2,
      4
    ]
  ],
  "root": 3,
  "nodes": [
    7,
    4,
    6
  ]
}

Output
5

FUNCTION SHAPE

edges: intMatrixroot: intnodes: intArray→int

SOLUTION NOTE

This is the same postorder LCA count idea as the two-node version, generalized from count == 2 to count == len(nodes).

Reveal reference solution +

pythonREFERENCE

def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
    targets = set(nodes)
    res = None

    def dfs(node):
        if not node:
            return 0
        nonlocal res
        left = dfs(node.left)
        right = dfs(node.right)
        curr = node in targets

        if res is None and left + right + curr == len(targets):
            res = node

        return left + right + curr

    dfs(root)
    return res

TimeO(n)

SpaceO(h + k)

Open on LeetCode ↗