43. Diameter of Binary Tree

아현·2021년 4월 23일
0

Algorithm

목록 보기
44/400
post-custom-banner

리트코드


  • 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라





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:
    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이라는 값을 부여한다.

    • 정 이진 트리 (Full Binary Tree)가 아닌 대부분의 경우에는 존재하지 않는 자식 노드에 -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이된다.

      • 정답은 거리값인 3이다.



➕ 중첩 함수에서 클래스 변수를 사용한 이유


  • 중첩함수 (Nested Function)를 사용할 때, 왜 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의 블로그]

profile
For the sake of someone who studies computer science
post-custom-banner

0개의 댓글