# 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:
longest: int = 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이라는 값을 부여한다.
이렇게 거슬러 올라가 최종 루트에서 상태값은 2, 거리는 3이 된다.
상태값은 리프노드에서 현재 노드까지의 거리다.
거리는 왼쪽 자식 노드의 상태값과 오른쪽 자식 노드의 상태값의 합에 2를 더한 값이다.
최종적으로 거리는 왼쪽 자식 노드의 리프노드에서 현재 노드까지의 거리(상태값)와, 오른쪽 자식 노드의 리프 노드에서 현재 노드까지의 거리(상태값)의 합에 2(현재 노드와 왼쪽, 오른쪽 자식 노드와의 거리)를 더한 것이다.
먼저 탐색함수부터 살펴본다.
계속 재귀 호출을 통해 왼쪽, 오른쪽의 각 리프 노드까지 DFS로 탐색한다.
이후 2개의 값을 계산하는데, 하나는 최종 결과가 될 가장 긴 경로 self.longest
나머지 하나는 앞서 얘기한 상태값 max(left, right) + 1
을 말한다.
자식 노드가 하나도 없는 경우 left, right
는 모두 -1이고, 이 경우 거리는 0, 상태값도 0이 된다.
자식 노드가 모두 존재하는 경우에는, 그리고 자식 노드가 둘 다 상태값이 0이라면, 거리인 a
는 2, 상태값인 b
는 1이 된다.
즉, 거리는 왼쪽, 오른쪽 자식 사이의 경로이므로 2를 더하게 되고, 상태값은 양쪽 자식 중 최대 상태값과 부모까지의 거리인 1을 더하게 된다.
위의 그림에서도 루트의 상태값은 2, 거리값은 3이된다.
longest
변수를 함수 내에서 선언하지 않고 바깥에 클래스 변수로 선언해서 번거롭게 self.longest
형태로 사용했을까?중첩 함수는 부모 함수의 변수를 자유롭게 읽어들일 수 있다.
그러나, 중첩 함수에서 부모 함수의 변수를 재할당하게 되면 참조 ID가 변경되며 별도의 로컬 변수로 선언된다.
self.longest = max(self.longest, left + right + 2)
라는 부분이 있다.
longest
변수에 값을 재 할당하는 부분인데 여기서는 self.longest
를 사용했다.
왜냐면 재할당을 해야 하기 때문이다. 따라서 부모 함수의 변수를 그대로 사용할 수 없었고, 함수 바깥에서 클래스 변수로 선언한 후 사용했다.
만약, longest
의 값이 숫자나 문자가 아니라 리스트나 딕셔너리 같은 자료형이라면 append()
등의 메소드를 이용해 재할당 없이 조작이 가능하다.
그러나, 숫자나 문자인 경우 불변 객체이기 때문에 중첩 함수 내에서는 값을 변경할 수 없다. 이 때문에 클래스 변수를 사용했다.
트리의 지름 (Diameter of Tree)
트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 트리의 지름이라고 한다. 이 트리의 지름을 가장 간단하게 구하는 방법은 다음과 같다.
트리의 임의의 한 노드 (u)에서 가장 멀리 있는 노드 (v)를 찾는다.
(v)에서 가장 멀리 있는 노드 (w)를 찾는다.
(v) ~ (w)가 트리의 지름이 된다.
위의 방법에서 특정 노드에서 가장 멀리 있는 노드는 DFS나 BFS를 사용하면 쉽게 찾을 수 있다.
증명은 귀류법을 이용하여 (v) ~ (w)가 아닌 다른 두 노드 (a) ~ (b)를 트리의 지름이라고 가정한 후, 이것이 모순이 됨을 보이면 된다. (자세한 내용은 여기를 참고하자)
출처: https://robustflame.tistory.com/entry/트리의-지름-Diameter-of-Tree [robustflame의 블로그]