[LeetCode/Python] 543.이진 트리의 직경(Diameter of Binary Tree)

 

 

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

 

 

Example:

 

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

 

Output: 3

 

Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

 

 

 

 

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 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: Optional[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

 

해설

 

가장 긴 경로를 찾는 방법은

 

일단 리프 노드까지 탐색한 다음

 

부모 노드로 거슬러 올라가면서 상태 값을 업데이트해 나가는 것이다.

 

상태 값은

 

리프 노드를 0으로 하고

 

위로 올라갈수록 +1되는 느낌으로 가고.

 

상태값이 하단에 적혀있다.

 

우리가 중요하게 여겨야 할 것은 longest인데

 

longest = left + right + 2이다.

 

이는 좀만 생각해보면 아! 할 거다.

 

상태 값을 누적해나가는 재귀 구조를 이해하고 나면

 

다른 트리 문제에서도 요긴하게 쓰일 것 같다.

 

 

 

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

 

중첩 함수는 부모 함수의 변수를 자유롭게 읽어들일 수 있지만

 

중첩 함수에서 부모 함수의 변수를 재할당하게 되면 참조 ID가 변경되며 별도의 로컬 변수로 선언된다.

 

따라서 부모 함수의 변수 값을 변경할 수 없다.

 

하지만 클래스 변수를 사용할 경우

 

재할당이 가능하여 이렇게 하였다.