인프런 커뮤니티 질문&답변
작성한 질문수
Lowest common ancestor of a binary tree문제 질문❓
해결된 질문
작성
·
95
1
Lowest common ancestor of a binary tree문제에서 아래 코드가 정답 코드로 알고 있는데,
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
if root == None:
return None
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if root.val == p.val or root.val == q.val:
return root
elif left and right:
return root
else:
return left or right
# elif left:
# return left
# elif right:
# return right
# else:
# reutrn None
위 코드에서 아래 부분을 해주는 이유가 무엇인지 궁금합니다.
if root.val == p.val or root.val == q.val:
return root
elif left and right:
return root
else:
return left or right답변 1
0
![[노씨데브 코치] 구운햄님의 프로필 이미지](https://cdn.inflearn.com/public/main/profile/default_profile.png?w=76){kind=avatar}
안녕하세요 Hey Jeong Park님!
질문주신 코드를 이해하기 위해서는 코드 전체의 의미를 파악해야 합니다.
class Solution:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
if root == None:
return None
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if root.val == p.val or root.val == q.val:
return root
elif left and right:
return root
else:
return left or right
본격적으로 살펴보기 전에 이 문제가 무엇인지 정확히 파악해야 합니다.
이 문제는 노드p와 노드q의 공통 조상이 어떤 것인지를 알아내야 하는 문제입니다.
어떻게 하면 공통 조상을 알아낼 수 있을까요?
이진트리니까.. 왼쪽과 오른쪽에서.. 뭔가를 찾았다는 신호를 보내주면 해결할 수 있지 않을까요?
잘 생각을 해보면.. 현재 노드에서 왼쪽을 순회하고.. 오른쪽을 순회했는데
양쪽에서 p와 q를 찾았다고 신호를 보내준다면? 그 의미는? 현재 노드가 p와 q의 공통 조상이라는 의미가 됩니다.
elif left and right:
return root이 부분이 위에서 말한 것과 일치합니다.
양쪽에서 p와 q를 찾았다면? 현재 노드를 반환하라
그러면.. 현재 노드가 p거나 q라면 어떻게 해아할까요?
그렇다면 현재 노드를 반환하면 됩니다.
여기서 가정을 해볼게요.
만약, 현재 노드가 p라면? 그런데 현재 노드에서 더 내려가면 q가 있다면?
더 내려갈 필요가 있을까요? 당연히 공통 조상은 p가 됩니다.
내려갔을 때 q가 없다고 하더라도 현재 노드를 반환하면 됩니다.
왜냐하면.. p를 찾았다는 신호를 보내줘야 하지 않을까요?!
지금까지.. 현재 노드가 p 혹은 q인 경우
그리고 양쪽에서 신호를 보내는 경우를 생각해봤습니다.
또 경우가 존재하죠? 한쪽에서만 신호를 보내거나 아예 신호를 보내지 않거나!
아예 신호를 보내지 않는다면? 여기서는 어떠한 것도 찾지 못했다는 의미이고.. 따라서 마찬가지로 신호를 보내지 않으면 됩니다.
한쪽에서만 신호를 보낸다면, 그 신호를 그대로 흘려보내면 됩니다.
왜냐하면.. 한쪽에서만 신호가 왔다는 의미는 적어도 현재 노드는 공통 조상이 아니라는 의미가 됩니다.
현재 노드보다 더 위에 공통 조상이 존재한다는 의미이기 때문에 자연스럽게 현재 노드에서 p 혹은 q를 찾았다는 신호만 위로 올려주면 됩니다.
else:
return left or right이 부분이 그렇습니다.
return left or right라는 코드가 약간 어렵게 느껴지나요?
저 코드는 left 혹은 right가 None이 아니라면 None이 아닌 값을 반환하고
둘다 None이라면 None을 반환하라는 의미입니다.
따라서 간단하게 말하면 양쪽 중에서 신호가 온 곳이 있다면 그 신호를 반환하고
없다면 신호없음(None)을 반환하라는 의미입니다.
이렇게 신호를 계속 반환하다보면..
elif left and right:
return root이 부분에서 만나지 않을까요?!
여기까지.. 이해가 잘 되었나요?
답변을 보신 후에 강의를 다시 한번 보시면 이해가 잘 되실 겁니다.
혹시라도 이해가 안된다면 또 질문 남겨주세요.
감사합니다.