[LeetCode 75] Medium - 236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

 

• LCA(최저 공통 조상) 찾기
• 노드 자신도 공통조상이 될수 있음
• 재귀로..
• 일단 루트가 none 이면 return 또는 return root
• 루트가 p 또는 q 인지 체크해서 맞으면 루트 반환
• 아니면, ..

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root: # 빈 노드면
            return ## return root

        if root == p or root == q:
            return root

        # 좌측에 lca 가 있으면, lca가 return 됨
        left = self.lowestCommonAncestor(root.left, p, q) 

        # 우측에 lca 가 있으면, lca가 return 됨
        right = self.lowestCommonAncestor(root.right, p, q) 

        if left and right: # 좌측에도 lca 가 있고, 우측에도 lca 가 있다면
            return root # 현재 노드(루트)가 공통 lca 라는 의미

        # 위의 조건이 해당없으면, left 와 right 중 하나는 null 일 것임
        # null 이 아닌것을 return 하면 됨
        return left or right # return left if left else right

 

https://youtu.be/7sY3-u8BkXM?si=5RHAUDkZ9tevN12x