[알고리즘] Leetcode #687 가장 긴 동일 값의 경로 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.

The length of the path between two nodes is represented by the number of edges between them.

 

입출력 예

Example 1:

 

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

Output: 2

 

Example 2:

 

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

Output: 2

 

Constraints

• The number of nodes in the tree is in the range [0, 104].
• -1000 <= Node.val <= 1000
• The depth of the tree will not exceed 1000.

 

Code

# 상태값 거리 계산 DFS
class Solution:
    result: int = 0
    
    def longestUnivaluePath(self, root):
        def dfs(node):
            if node is None:
                return 0
            
            # 존재하지 않는 노드까지 DFS 재귀 탐색
            left = dfs(node.left)
            right = dfs(node.right)

            # 동일값 판별 (부모노드 - 자식노드)
            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

트리 너무 재밌다,, leetcode에 TreeNode라는 클래스가 구현되어 있어서 자식 노드들을 left, right로 쉽게 접근할 수 있다. 이렇게 리프 노드까지 도달하도록 한 후, 부모노드와 자식 노드의 값이 같을 때 1을 추가한다. 이때, 재귀 형태이므로 result에는 양쪽 자식 노드들로부터 저장된 거리의 합을 담고, 양쪽 노드 중 더 큰 거리를 리턴한다. (현재 노드의 부모노드에서는 둘 다 선택하는 방향으로 갈 수 없기 때문: 단방향) 최종적으로는 이렇게 값이 큰 쪽만 고려해 계산된 최대 거리를 반환하도록 한다. (최상단 노드는 양쪽 자식 노드에서 단 방향으로 선택한 최대 거리를 합한 값을 가짐)