Lowest Common Ancestor
아이디어
문제 해결을 위해서 필요한 경우의 수를 생각해보자면 다음과 같다.
- 내가 q나 p중 하나인 경우 -> 나를 return
- 내가 q나 p중 하나가 아닌데 조상이 p나 q인 경우( or lowestCommonAncestor인 경우) -> 조상을 return
- 내가 q나 p중 하나가 아닌데 조상도 p나 q인가 아닌 경우( or lowestCommonAncestor인 경우) -> None을 return
- 내가 lowest common ancestor인 경우 -> 나를 return
tree가 다음과 같이 구성이 되어있다고 가정할 때,
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None내가 p나 q인 경우, 나 자신을 return 하고 내가 p나 q가 아닌 경우 left나 right를 return한다.
이 때, left나 right가 None일 경우 None이 return 된다.
- 나 자신이 조건일 때는 left나 right만 return을 받다가 나 자신을 return을 해주게 된다.
- 내가 lowestCommonAncestor일 때는 첫 번째 조건문인
if root == q or root == q :부분을 통과한 후
elif left and right : 문에서 조건이 충족되어 나 자신을 return하게 된다. 3. 내가 p나 q도 아니지만 내 자식이 p나 q인 경우
return left or right에서 p나 q인 자식을 통과시켜 준다. 4. 내가 p나 q도 아니고 자식도 p나 q가 아닌 경우
return left or 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)
# 내가 p나 q중 하나일 경우
# 상위 호출자에게 내가 left나 right라고 전달해줌
if root == p or root == q :
return root
# left와 right가 모두 있을 경우
elif left and right :
return root
# left도 right도 None인 경우
# 최하단 Node인데 p, q 둘 중 어디에도 해당 안함
# None을 return
# 만약에 left right 중 값이 들어왔다면 해당 값을 전달
return left or right조건을 쓰고 보니까
if root == p or root == q :
return root
# left와 right가 모두 있을 경우
elif left and right :
return root이 부분의 조건을 하나로 묶어도 됐을 것 같다.