[LeetCode/Python] 687.가장 긴 동일 값의 경로(Longest Univalue Path)

 

 

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

 

 

Example

 

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

 

Output: 2

 

 

 

 

 

1. 상태 값 거리 계산 DFS

 

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    result = 0
 
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node: TreeNode):
            if not node:
                return 0
            
            # 존재하지 않는 노드까지 DFS 재귀 탐색
            left = dfs(node.left)
            right = dfs(node.right)
            
            # 현재 노드가 자식 노드와 동일한 경우 거리 1 증가
            if node.left and node.left.val == node.val:
                left += 1
            else:
                left = 0
            if node.right and node.right.val == node.val:
                right += 1
            else:
                right = 0
            
            # 왼쪽과 오른쪽 자식 노드 간 거리의 합 최댓값이 결과
            self.result = max(self.result, left + right)
            # 자식 노드 상태값 중 큰 값 리턴
            return max(left, right)
        
        dfs(root)
        return self.result

 

 

해설

 

리프 노드까지 DFS으로 탐색해 내려간 다음

 

값이 일치할 경우 거리를 차곡차곡 쌓아 올려가며 백트래킹 하는 형태로 풀이하였다.

 

result는 동일 값의 길이니까 left + right가 맞고

 

다만 return되는 값은 result랑 상관없이 그 부분에서의 상태 값인 거니까

 

left와 right 중에 큰 값을 선택한다.