트리 문제 질문입니다!

Question

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 중 둘 중 하나 존재하는 것을 리턴하라는 의미구요   저는 자바로 하고있는데 저부분이 이해가 안가서 질문드립니다..!

개발남노씨 · Answer

안녕하세요 민지님!! 일단 코드에 약간 오류가..! 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에서만 쓰이는 형태일 수 있는데요, 이해를 도와드리기위해 제가 예시 사진을 가져와봤습니다. 혹시 보시고 이해안가시는게 있으면 언제든 질문 주세요 :)