Leetcode 1123. Lowest Common Ancestor of Deepest Leaves

Problem statement

https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

Solution

The idea is to use LCA approach with postorder dfs, where we keep information: (deepest children of node, distance from node to root, node). We update our answer if we found deeper leaf or if we have the same depth of leaf and we have both the deepest leafs in the left and in the right subtrees, than we now that we need to update our node.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def lcaDeepestLeaves(self, root):
        self.ans = (0, 0, None)
        def dfs(lvl, node):
            if not node: return 0
            lft = dfs(lvl + 1, node.left)
            rgh = dfs(lvl + 1, node.right)
            cand = (max(lft, rgh) + 1 + lvl, lvl, node)

            if cand[0] > self.ans[0] or cand[0] == self.ans[0] and lft == rgh:
                self.ans = cand
          
            return cand[0] - cand[1]
        
        dfs(0, root)
        return self.ans[2]