• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

root == p 를 비교하는법?

23.03.26 01:01 작성 조회수 259

1

강사님의 풀이방법을 보면

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
      
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if root == p or root == q:
            return root
        elif left and right:
            return root
        return left or right

여기서 root.value == p가 아니라 어떻게 root == p로 비교할 수 있는 지 궁금합니다.

아래는 제가 푼 방식입니다.

class Node:
    def __init__(self, value=0, left=None, right = None):
        self.value=value
        self.left= left
        self.right = right

def LCA(root,p,q):
    if root is None:
        return None
    left = LCA(root.left,p,q)
    right = LCA(root.right,p,q)
    if root.value == p or root.value ==q:
        return root
    elif left and right:
        return root
    return left or right

root=[3,5,1,6,2,0,8,None,None,7,4]
root = Node(value = 3)
root.left = Node(value = 5)
root.right = Node(value = 1)
root.left.left = Node(value = 6)
root.left.right = Node(value = 2)
root.right.left = Node(value = 0)
root.right.right = Node(value = 8)
root.left.right.left = Node(value = 7)
root.left.right.right = Node(value = 4)

root= LCA(root,5,6)
print(root.value)

 

  if root.value == p or root.value ==q:
        return root

저는 여기서 root == p 를 하게 되면 아래 오류가 발생합니다.

AttributeError: 'NoneType' object has no attribute 'value'

 

답변주시면 정말 감사하겠습니다.

답변 1

답변을 작성해보세요.

0

안녕하세요 코먹하님

코먹하님께서 제대로 코드 구현을 하셨습니다.

제 코드의 경우에는 leetcode의 채점시스템상에서 잘 작동하더라구요.

 

image리트코드에서 input 값으로 주어지는 것들이([3, 5, 1 , ..] p = 5, p =1) 이런 값들이 int형 값이 아니라, node를 지칭하는 겁니다.

 

그래서 아마 코먹하님의 코드

root.val == p 

이게 오히려 작동하지 않을거에요

root == p 

이렇게 코드를 작성해야 될겁니다. 같은 노드를 가리키나봐요.

 

또는 이게 좀 더 정확하겠죠.

root.val == p.val

 

저도 혼자 테스트케이스를 작성해서 코드를 작성할 때에는 코먹하님과 같은 형태로 코드를 작성했습니다.

image

 

학습에 참고하시길 바랄게요 :)

또 궁금하신점 있으시면 어제든 질문주세요!