설명

LeetCode의 Longest Univalue Path 문제다.

트리가 주어졌을 때 같은 값(Univalue)의 최장 경로 길이를 구하는 문제다. 이때 '경로'란 노드들이 연결되어 있어야 하기 때문에 경로의 길이는 해당 노드들의 간선의 갯수가 된다.
문제에서 주어진 위의 예시처럼 현재 트리에서 같은 값의 최장 경로는 첫 번째 노드부터 오른쪽 자식 노드로만 이어진 노드 '5'의 경로로 2개의 간선으로 이루어져 있기 때문에 2가 된다.
하지만 경로가 꼭 첫 번째 그림처럼 일직선이지 않아도 된다. 위의 그림처럼 꺾여있더라도 어쨌든 경로만 구성되면 되기 때문에 루트 노드에서 탐색하기보다 말단 노드에서 거꾸로 탐색하는 풀이를 생각해볼 수 있다.

풀이

기본적인 아이디어는 트리의 노드를 말단 노드까지 재귀탐색한 후 자신의 양 쪽 자식 노드 중 현재 노드와 같은 값의 노드의 Univalue Path의 길이를 1씩 늘려가며 갱신하는 방법이다.
위의 예시와 비슷한 트리를 예로 들어보면 왼쪽 노드 우선, 그리고 오른쪽 노드 순서로 말단 노드까지 탐색했을 때 일단 노드 하나로는 경로를 구성할 수 없기 때문에 최장 거리는 0이다.
그리고 재귀 호출이 끝나고 부모 노드로 돌아왔을 때 현재 노드와 왼쪽, 오른쪽 자식 노드를 비교하여 같은 값, 즉 Univalue라면 Univalue Path에 간선이 추가된 것이므로 경로의 길이를 증가시킨다.

그리고 왼쪽 자식 노드에서 현재 노드를 걸쳐 오른쪽 자식 노드까지 이어질 수 있는 구조기 때문에 왼쪽 자식 노드의 Univalue Path 거리와 오른쪽 자식 노드의 Univalue Path 거리를 합해서 최장 거리값을 갱신한다. 이 경우 위처럼 거리 2의 4 값을 가진 노드들의 Univalue Path가 구축된다.
그 다음에는 부모 노드에게 왼쪽 자식 노드나 오른쪽 자식 노드 중 더 긴 Univalue Path를 넘겨줘야 한다. 이는 마치 트리의 높이를 구하는 것과 비슷한데 대신 부모 노드에서는 현재 노드와 자식 노드의 값을 비교해서 동일한 경우에만 반환값을 활용하여 Univalue Path를 이어나가게 된다.

위의 그림의 경우 왼쪽 자식 노드와 오른쪽 자식 노드의 Univalue Path의 길이가 동일하기 때문에 아무거나 반환해도 상관 없지만 왼쪽 자식 노드의 Univalue Path 길이를 반환했다고 가정할 때 루트 노드에는 1이 반환된다. 그러나 노드 1과 노드 4는 다르기 때문에 Univalue Path 계산에 활용되지 않으며(0으로 취급) 최장거리는 갱신되지 않는다.

이 과정을 말단 노드부터 루트 노드까지 재귀적으로 수행하면 최장 거리를 얻을 수 있으며 이를 기반으로 구현한 코드는 다음과 같다.

class Solution:
    # 재귀 함수에서 접근하기 위한 전역 변수.
    longestUnivalue = 0
    
    # 재귀 호출 함수.
    def findLongestUnivaluePath(self, node):
        # 말단 노드의 자식 노드라면 탐색 종료.
        if node is None:
            return None
        
        # 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 재귀 탐색.
        leftResult = self.findLongestUnivaluePath(node.left)
        rightResult = self.findLongestUnivaluePath(node.right)
        
        # 왼쪽 자식 노드와 현재 노드가 같은 값이라면 Univalue Path 길이 증가.
        # 같은 노드가 아니라면 Univalue Path가 끊긴 것이므로 길이 초기화.
        if node.left and node.left.val == node.val:
            leftResult += 1
        else:
            leftResult = 0
        # 오른쪽 자식 노드와 현재 노드가 같은 값이라면 Univalue Path 길이 증가.    
        # 역시 같은 노드가 아니라면 Univalue Path가 끊긴 것이므로 길이 초기화.
        if node.right and node.right.val == node.val:
            rightResult += 1
        else:
            rightResult = 0
        
        # 현재 노드까지 포함한 Univalue Path의 길이 갱신.
        # 위에서 경로가 끊겼다면 0으로 초기화했기 때문에 Univalue 조건 준수 가능.
        self.longestUnivalue = max(self.longestUnivalue, leftResult + rightResult)
        # 더 긴 Univalue Path의 길이를 반환.
        return max(leftResult, rightResult)
    
    
    def longestUnivaluePath(self, root: TreeNode) -> int:
        # 기본적인 예외처리.
        if root is None:
            return 0
        
        # 루트 노드부터 탐색 시작 및 최장거리 반환.
        self.findLongestUnivaluePath(root)
        return self.longestUnivalue

후기

트리의 높이를 구하는 로직을 응용하는 풀이가 인상깊었던 문제다. Univalue Path라는 개념을 잘못 알고 있어서 경로 내 포함된 노드의 갯수로 풀이를 작성햇다가 간선의 갯수라는걸 알고 풀이를 뜯어고친 기억이 있다. 그 외에도 현재 노드를 포함해서 양쪽 자식 노드로 이어지는 Univalue Path 등 생각할 거리가 많은 문제였다.