인프런 커뮤니티 질문&답변

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if root is None: # check whether Node is empty
            return
        if root is p or root is q:
            return root
        
        # root 노드가 p 또는 q가 아니면 순회하도록 재귀함수 호출
        l = self.lowestCommonAncestor(root.left, p, q) # code 1
        r = self.lowestCommonAncestor(root.right, p, q) # code 2
        
        # p와 q 조건 검사를 마친 후(모든 노드를 순회하는 것은 아님)
        if l and r:
            return root
        elif l:
            return l
        else:
            return r

먼저 LCA함수를 호출하면 root가 가리키는 노드가 있는지 체크한 다음에 계속해서 p 또는 q 노드가 맞는지 확인을 합니다. 만약 p 또는 q 노드가 아니면 재귀함수를 호출해서 자식 노드로 더 깊이 순회하도록 만듭니다. 역시 자식 노드들도 p 또는 q 노드가 맞는지 검사한 후 맞으면 l 또는 r에 그 노드를 저장합니다.

여기서 궁금한 점은, 자기 자신이 공통 조상이 될 때인데요. 이렇게 되면 더 깊이까지 탐색하지 않아도

elif l: return l 에 의해서 왼쪽만 탐색했으니까 시간복잡도가 O(logN)인가요? 아니면 다른 케이스들도 고려해서 최악의 경우 모든 노드를 탐색해야되니까 O(N)이 되는건가요?