Leetcode 1676 Lowest Common Ancestor of a Binary Tree IV

Problem statement

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/

Solution

We can solve this problem in almost the same way we solved 0236. Lowest Common Ancestor of a Binary Tree. The idea is to use dfs(node) function, which return how many nodes from nodes is in subtree. To find number of such nodes we need to use postorder dfs, where we look at the left and at the right subtrees first and also at node itself. If we see that lft + rgh + mid == len(nodes), we found our node, so we mark self.Found = node. Notice that we looking for LCA, so if we meet CA later, we do not need to save them.

Complexity

Time complexity is O(n), space complexity is O(h).

Code

class Solution:
    def lowestCommonAncestor(self, root, nodes):
        nodes_set = set(nodes)
        def dfs(node):
            if not node: return 0
            lft = dfs(node.left)
            rgh = dfs(node.right)
            mid = node in nodes_set
            if lft + rgh + mid == len(nodes):
                if not self.Found: self.Found = node
            return lft + rgh + mid
        
        self.Found = None
        dfs(root)
        return self.Found