-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
트리 문제 질문입니다!
23.03.09 16:16 작성 조회수 267
1
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 righthttps://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 중 둘 중 하나 존재하는 것을 리턴하라는 의미구요
저는 자바로 하고있는데 저부분이 이해가 안가서 질문드립니다..!
답변을 작성해보세요.
1
개발남노씨
지식공유자2023.03.09
안녕하세요 민지님!!
일단 코드에 약간 오류가..!
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에서만 쓰이는 형태일 수 있는데요,
이해를 도와드리기위해 제가 예시 사진을 가져와봤습니다.
혹시 보시고 이해안가시는게 있으면 언제든 질문 주세요 :)
답변 1