책 풀이
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
longest = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def dfs(node: TreeNode) -> int:
if not node:
return -1
# 왼쪽, 오른쪽의 각 리프 노드까지 탐색
left = dfs(node.left)
right = dfs(node.right)
# 가장 긴 경로
self.longest = max(self.longest, left + right + 2)
# 상태값
return max(left, right) + 1
dfs(root)
return self.longest
가장 긴 경로를 찾는 방법은 먼저 가장 말단, 즉 리프 노드까지 탐색한 다음 부모로 거슬로 올라가면서 각각의 거리를 계산해 상태값을 업데이트하며 누적해 나가는 것이다. 그림에서 보면 존재하지 않는 노드에도 -1이라는 값을 부여하는데, 존재하지 않는 자식 노드에 -1을 부여해 페널티를 주기 위함이다.
최종적으로 거리는 왼쪽 자식 노드의 리프 노드에서 현재 노드까지의 거리(상태값)와, 오른쪽 자식 노드의 리프 노드에서 현재 노드까지의 거리의 합에 2(현재 노드와 왼쪽, 오른쪽 자식 노드와의 거리)를 더한 값과 같다.
logest 변수를 함수 내에서 선언하지 않고 바깥에 클래스 변수로 선언해서 번거롭게 self.longest 형태로 사용한 이유가 있다. 중첩 함수는 부모 함수의 변수를 자유롭게 읽어들일 수 있다. 그러나 중첩 함수에서 부모 함수의 변수를 재할당하게 되면, 참조 ID가 변경되며 별도의 로컬 변수로 선언된다.
