leetcode 236 python 파이썬 소스코드 + LCA(최소공통조상)

문제링크

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-interview-150

📢 문제 간략설명

p , q 의 값을 바탕으로 LCA 값 찾기

📌풀이 알고리즘

< 기본 LCA 알고리즘 >
1. 두 정점의 깊이를 같게 만들어준다.
2. 한 칸씩 부모 정점으로 이동하여 같은 정점이 나올때까지 반복
3. 처음으로 만나는 같은 정점이 최소 공통 조상이 됨.
링크텍스트

< 문제 알고리즘 >
1. root부터 시작하여 좌측, 우측 서브트리 확인
2. 해당 서브트리의 값이 p 혹은 q의 값과 동일하다면 해당 노드(root)가 LCA 이므로 반환
3. 좌측, 우측 서브트리 재귀호출
4. left나 right 값 둘 중 하나라도 None 이라면 왼쪽이나 오른쪽에 p와 q가 동시에 몰려있다는 뜻 이므로, left or right를 반환

📌소스코드 및 풀이방법 (1)

좌측 서브트리와 우측 서브트리를 기준으로 함수를 재귀적으로 호출
시간복잡도 : O(n)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        
        if root == p or root == q : 
            return root

        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)

        if left and right: 
            return root
        else: 
            return left or right
            #left가 있으면 left를 반환하고 right가 있으면 right를 반환함.
        

문제후기 및 학습

나는 멍청이당 ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ
레전드 돌머ㄹ ㅣ ㅜㅜ
나만 생각 못 해내는거야 ? ㅇㅇ ㅜ

참고
알고리즘 구현방식 참고
https://davincicoding.tistory.com/35
풀이참고
https://www.youtube.com/watch?v=WO1tfq2sbsI