트리 문제 질문입니다!

def LCA(root, p, q):
    if root == None:
        return None
    
    left = LCA(root.left, p, q)
    right = LCA(root.right, p, q)

    if root == p or root == 1:
        return root
    elif left and right:
        return root
    return left or right

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

이 문제 질문드립니다.

맨 밑에 코드가 이해가 안가서 질문드려요

root가 q 이거나 p 이면 root를 반환하는 것 까지 이해했습니다.

    elif left and right:
        return root
    return left or right

저 부분이 잘 이해가 안됩니다

elif left and right 의 의미가 left 랑 right 둘다 존재하면 root를 반환하라는 의미인가요?

그게 아니면 left 아니면 right 중 둘 중 하나 존재하는 것을 리턴하라는 의미구요

저는 자바로 하고있는데 저부분이 이해가 안가서 질문드립니다..!

안녕하세요 민지님!!

일단 코드에 약간 오류가..!

if root == p or root == q:

이거 맞죠?? q대신 1이 적혀있어서 ㅎㅎ

질문에 대한 답을 드리자면

left와 right에 어떤 값이 있는지는 총 4가지 경우의 수가 존재합니다.

left == None // right == None
left == 값존재 // right == None
left == None // right == 값존재
left == 값존재 // right == 값존재

elif left and right 의 의미는 left와 right값이 모두 값이 존재할 때 root를 반환한다 라는 뜻이에요.
즉 4번 째 경우의 수일 때 root를 반환하는거죠.

left와 right의 값이 둘다 존재한다는 뜻은 뭘까요?? 현재 노드가 "최소 조상 노드 LCA" 라는 뜻입니다.

그렇기 때문에 값이 둘 다 존재할 때 root를 반환하는거죠! 내가 최소조상 노드야!!! 하면서 나 자신을 반환하는 겁니다. (여기서 root는 전체 트리의 root가 아니라, cur_node를 가리키는겁니다)

그렇다면 elif left and right를 만족하지 못하고 건너뛰면 어떤 경우의 수가 남냐

left == None // right == None
left == 값존재 // right == None
left == None // right == 값존재

이렇게 세 가지 경우의 수가 남겠죠.

첫 번째 상황부터 볼까요

left == None // right == None 일때는 그냥 None을 반환해주면 돼요

left == 값존재 // right == None
left == None // right == 값존재

이 상황에서는 값이 존재하는 쪽의 값만 전달해주면 됩니다.

그걸 조건문 여러개를 써서 구현할 수 있지만,

return left or right로 구현하게되면

left == None // right == None
left == 값존재 // right == None
left == None // right == 값존재

이 세 가지 경우의 수를 그냥 한줄에 구현할 수 있게 돼요

사실 이건 파이썬이나 JS에서만 쓰이는 형태일 수 있는데요,

이해를 도와드리기위해 제가 예시 사진을 가져와봤습니다.

혹시 보시고 이해안가시는게 있으면 언제든 질문 주세요 :)

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