Python 알고리즘 인터뷰 - 문제 44. 가장 긴 동일 값의 경로

leetcode 687. https://leetcode.com/problems/longest-univalue-path/description/

 

문제

동일한 값을 지닌 가장 긴 경로를 찾아라

 

예제

입력 : [5,4,5,1,1,None,5]

출력 : 2

 

입력 : [1,4,5,4,4,None, 5]

출력 : 2

 

풀이

value 리턴 값을 비교하여 풀이한 방법

43.번 문제와 유사하게 두 노드간의 경로를 구하는 문제이나 대신 동일한 값으로 연결이 되어야하는 조건이 생겼다. left의 value와, right value를 현재 노드의 value와 비교하여 같은 경우 경로를 갱신하며, 다른 경우는 pass하는 방식으로 구현한다.

 

dfs 함수에서 좌, 우의 노드 value, length를 계산하여 가져온다.

def dfs(node):
    if not node:
        return None, 0

    left_value, left_length, = dfs(node.left)
    right_value, right_length = dfs(node.right)

 

함수가 반환되는 경우 left_value, right_value가 각각 현재 value와 다를 경우 값을 0으로 초기화한다.

if node.val != left_value:
    left_length = 0

if node.val != right_value:
    right_length = 0

 

이후 longest를 left, right value값을 더한 값을 비교하여 더 큰 값을 갱신한다. node value값과 좌, 우 길이 중 max값에 +1을 하여 값을 반환한다.

self.longest = max(self.longest, left_length + right_length)
return node.val, max(left_length, right_length) + 1

해당 코드는 node.val과 값이 다른 경우 left_length, right_length가 0으로 되기 값이 동일한 노드의 length만 반영되도록 한다.

현재 노드와 값이 같은 노드의 길이만 갱신 및 반환된다.

전체 코드

class Solution(object):
    longest = 0

    def longestUnivaluePath(self, root):
        if not root:
            return 0

        def dfs(node):
            if not node:
                return None, 0

            left_value, left_length, = dfs(node.left)
            right_value, right_length = dfs(node.right)

            if node.val != left_value:
                left_length = 0

            if node.val != right_value:
                right_length = 0

            self.longest = max(self.longest, left_length + right_length)
            return node.val, max(left_length, right_length) + 1

        dfs(root)
        return self.longest