[파이썬 알고리즘 인터뷰] 19. 가장 긴 동일 값의 경로

1. 문제 

LeetCode 687. Longest Univalue Path

이진트리 root 가 주어지면 같은 값으로 이어진 경로 중 가장 긴 경로의 길이를 리턴하여라.

 

2. 풀이

 

 

dfs 방식을 이용해서 풀었다.

 

함수가 노드를 인자로 받으면 현재 노드부터 아래로 이어지는 같은 값을 가진 노드 경로 길이를 state에 저장해 리턴한다. 또한 클래스 변수 longest를 만들고, 경로를 탐색하는 중 가장 긴 경로가 새롭게 등장하면 longest의 값을 업데이트했다.

 

 우선 리프노드가 state가 0을 가지게 하기 위해서 현재 노드가 존재하지 않는다면 -1을 리턴한다. 그리고 왼쪽/오른쪽 자식 노드에 대해 재귀호출을 실행하고, 그 결과로 return된 state 값을 right, left 변수에 저장한다.

 모든 자식 노드가 자신과 값이 같다면 left+right에 왼쪽/오른쪽 자식 노드에서 자기로 오는 거리 2를 더한 값, 기존 longest의 값 중 큰 값으로 클래스 변수 longest의 값을 업데이트한다. state는 자식 노드의 state 중 더 큰 값에 자식 노드에서 자신까지 오는 거리를 더해 그보다 하나 큰 값으로 설정한다. 오른쪽 노드와 자신의 값이 같다면 longest는 right에 자신으로 오는 거리 1을 더한 값, 기존 longest 중 큰 값으로 설정한다. state는 오른쪽 노드의 state에서 자신까지 오는 1을 더해서 설정한다. 왼쪽 노드에 대해서도 같은 작업을 실행한다. 마지막으로 자식 노드 중 같은 값이 없다면 0을 리턴한다.

 

 

 

3. 코드 

전체 코드는 다음과 같다.

 

longest:int = 0
def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
    def DFS(node: Optional[TreeNode]) -> int:
        right_val = -1
        left_val = -1

        if not node:
            return -1

        left = DFS(node.left)
        right = DFS(node.right)

        if node.left:
            left_val = node.left.val

        if node.right:
            right_val = node.right.val

        if right_val == node.val and left_val == node.val:
            self.longest = max(self.longest, left + right + 2)
            state = max(left, right) + 1
        elif right_val == node.val:
            self.longest = max(self.longest, right + 1)
            state = right + 1
        elif left_val == node.val:
            self.longest = max(self.longest, left + 1)
            state = left + 1
        else:
            state = 0

        return state

    DFS(root)

return self.longest