Lowest Common Ancestor of Deepest Leaves LeetCode solution in Python

1
# Runtime: 112 ms (Top 7.97%) | Memory: 14.4 MB (Top 40.85%)
2
class Solution:
3
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
4

5
        self.max_lvl = (0, [])
6
        self.pathes = {}
7

8
        def rec(root, parent, lvl):
9
            if not root:
10
                return
11
            if lvl > self.max_lvl[0]:
12
                self.max_lvl = (lvl, [root])
13
            elif lvl == self.max_lvl[0]:
14
                self.max_lvl = (lvl, self.max_lvl[1] + [root])
15
            self.pathes[root] = parent
16
            rec(root.left, root, lvl + 1)
17
            rec(root.right, root, lvl + 1)
18

19
        rec(root, None, 0)
20
        print(self.max_lvl)
21
        # for key in self.pathes:
22
        # if key!=None and self.pathes[key]!=None:
23
        # print(key.val,"-",self.pathes[key].val)
24
        if len(self.max_lvl[1]) < 2:
25
            return self.max_lvl[1][0]
26
        parent = self.max_lvl[1]
27
        while len(parent) > 1:
28
            temp = set()
29
            for p in parent:
30
                temp.add(self.pathes.get(p, None))
31
            parent = temp
32
        return parent.pop()