Problem statement

https://binarysearch.com/problems/Lowest-Common-Ancestor/

Solution

Equal to Leetcode 1644 Lowest Common Ancestor of a Binary Tree II.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def solve(self, root, p, q):
        self.arr, self.dep = [], []  #euler path
        def dfs(node, depth):
            self.arr += [node.val]
            self.dep += [depth]
            for child in filter(None, [node.left, node.right]):
                dfs(child, depth + 1)
                self.arr += [node.val]
                self.dep += [depth]
            
        dfs(root, 0)
        print(self.arr)
        i1, i2 = self.arr.index(p), self.arr.index(q)
        i1, i2 = min(i1, i2), max(i1, i2)

        return self.arr[min(range(i1, i2), key = lambda x: self.dep[x])]