문제
동일한 값을 지닌 가장 긴 경로를 찾아라.
입력
출력
2
입력
출력
2
코드
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
result: int = 0
def longestUnivaluePath(self, root: TreeNode):
def dfs(node: TreeNode):
if node is None:
return 0
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풀이
루트 노드에서 DFS로 재귀 탐색을 진행하면서 리프에 도달하면 그때부터 백트래킹하면서 거리를 누적해나간다.
def dfs(node: TreeNode):
...
left = dfs(node.left)
right = dfs(node.right)이렇게 재귀 호출로 내려가면 left, right는 각각 리프 노드에 이르러서 값을 리턴받게 된다. 더 이상 존재하지 않는 노드까지 내려가게 되면 다음과 같은 형태로 리턴한다.
if node is None:
return 0존재하지 않는 노드까지 내려가게 되면 거리 0을 리턴한다. 이제 이 값이 점점 백트래킹 되면서 증가할 것이다. 이 문제는 동일 값 여부를 판별해 거리를 계산하는 문제이기 때문에, 다음과 같이 자식 노드가 동일한 값인지 확인하는 과정이 필요하다.
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왼쪽과 오른쪽 자식 노드를 각각 확인해서 현재 노드, 그러니까 부모 노드와 동일한 경우 각각 거리를 1 증가한다. 이제 다음과 같이 왼쪽 자식과 오른쪽 자식 노드 간 거리의 합을 결과로 한다.
result = max(result, left + right)합이 가장 큰 값을 최종 결과로 한다. 이제 다음번 백트래킹 시 계산을 위해 앞서 문제와 유사하게 상태값을 셋팅해서 부모 노드로 올려야 한다. 다음과 같이 부모 노드를 위해 현재까지의 거리를 리턴해준다.
return max(left, right)현재 노드는 양쪽 자식 노드를 모두 연결할 수 있지만 현재 노드의 부모 노드에서는 지금의 양쪽 자식 노드를 모두 연결할 수 없다. 단방향이므로 양쪽 자식 노드 중 어느 한쪽 자식만 택할 수 있으며, 이는 트리의 특징이기도 하다. 따라서 둘중 큰 값을 상태 값으로 리턴해준다. 어차피 한 군데만 방문할 수 있다면 더 큰쪽을 방문하는 게 낫기 때문이다.
헷갈렸던 부분
result = max(result, left + right)left 자식 노드, right 자식 노드와 현재 노드를 비교하여 left, right를 업데이트 해준 뒤, 그 업데이트 된 값을 더해서 result를 계산. 즉, 예제의 루트노드로 보자면 0 + 2로 result가 계산된다.
return max(left, right)거리 자체가 한가지 길로 계속 이어져야지 left, right 두가지길로 나뉘어지면 안된다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]