파이썬 알고리즘 인터뷰 - 가장 긴 동일 값의 경로

문제

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

입력

Input: root = [5,4,5,1,1,5]

출력

Output: 2

처음에 지나온 노드의 개수 인줄 알고 엥? 왜 2개이지 한참 고민했다. 출력을 다시 생각해보니 간선의 개수였다...
아무튼 이 문제도 처음 접근하는 나에게는 어려운 친구들이었다. 역시 그냥은 잘 안 풀려서 책에 도움을 받았다.
뭐 어떤가..잘 이해해서 내걸로 만들면되지!

def longestUnivaluePath(root) -> int:
    rtn = [0]
    def dfs(node:TreeNode):
        if node is None:
            return 0
        #왼쪽 노드 값도 구해와 줄래?
        left = dfs(node.left)
        #오른쪽 노드 값도 구해와 줄래?
        right = dfs(node.right)

        if node.left and node.val == node.left.val:
            left += 1
        else:
            left = 0

        if node.right and node.val == node.right.val:
            right += 1
        else:
            right = 0
        #왼쪽 노드와 오른쪽 노드의 값을 더해 경로 값을 리스트에 담는다.
        rtn.append(left+right)
        # 왼쪽과 오른쪽 큰쪽을 반환 해준다.
        return max(left,right)
        
    #루트 노드 부터 시작한다.
    dfs(root)
    #rtn 리스트의 가장 큰 값을 반환한다.
    return max(rtn)

먼저 루트 노드부터 우측 리프 노드까지 이동 거리를 구하는 과정을 생각해보면 첫번째로 if문으로 node에 값이 없으면 0을 반환해준다.

재귀적 코드는 조금 이따가 설명하고, 먼저 현재 노드의 값과 left 노드의 값이 같으면 동일한 값이니까 이때 left 변수에 값을 +1 해준다.
right도 마찬가지다. 그런 다음 left 값과 rifgt 값을 더해 rtn 리스트에 넣어준다.

그리고 left값과 right 값중에 큰 값을 다시 반환해주면서 큰 값의 left노드 right 노드 값을 재귀적으로 값을 구한다.
모든 재귀 문이 종료되면 rtn 리스트에는 최종적으로 계산한 값들이 쌓이는데, 이 값중에 가장 큰값을 리턴해주면 우리가 원하느 답을 얻을 수 있다.

그리고 rtn을 전역변수로 사용했는데 이렇게 하면 내 테스트 코드에서도 확인 하기가 쉬워서 저런 방식으로 바꿔봤다.

전에 이진 트리의 직경 문제를 이해하고 왔더니 이문제는 어느정도 이해하기 수월했다.
아직 손으로 잘 써지지는 않지만 계속 상기시켜서 이진트리의 연산구조를 확실히 하면 될 것 같다.

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

Longest Univalue Path - LeetCode