Different python O(N) solution, easier to code in an interview than other methods


  • 0
    N

    The idea is using dfs to find the two paths to p and q respectively, and compare the two paths one by one until they don't agree. The code is longer than other solutions, but runs in O(N) and is extremely easy to come up with in an interview.

    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            pathp, pathq = [], []
            self.helper(root, p, [], pathp)
            self.helper(root, q, [], pathq)
            i = 0
            self.pathp, self.pathq = pathp[0], pathq[0]
            # compare the two paths one by one, until one goes out of range or the two don't equal
            while i < len(self.pathp) and i < len(self.pathq) and self.pathp[i] == self.pathq[i]:
                i += 1
            return self.pathp[i-1]
        
        def helper(self, root, p, path, pathp):
            # put the final path into pathp
            if root is None:
                return 
            if root == p:
                pathp.append(path + [p])
                return
            path.append(root)
            self.helper(root.left, p, path, pathp)
            self.helper(root.right, p, path, pathp)
            path.pop()
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.