이진 트리의 직경

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

https://leetcode.com/problems/diameter-of-binary-tree/

Diameter of Binary Tree - LeetCode

 

 가장 긴 경로를 찾는 방법은 먼저 가장 말단, 즉 리프 노드까지 탐색한 다음 부모로 거슬러 올라가면서 각각의 거리를 계산해 상태값을 업데이트 하면서 다음과 같이 누적해 나가면 된다.

정 이진 트리가 아닌 대부분의 경우에는 존재하지 않는 자식 노드에 -1을 부여해 패널티를 준다

 최종 루트에서 상태값은 2, 거리는 3이 된다.

 

 상태값은 리프 노드에서 현재 노드까지의 거리다.

 

 거리는 왼쪽 자식 노드의 상태값과 오른쪽 자식 노드의 상태값의 합에 2를 더한 값이다.

 

 

이처럼 재귀 호출을 통해 왼쪽, 오른쪽의 각 리프 노드까지 DFS로 탐색한다

 self.longest는 최종 결과가 될 가장 긴 경로(거리), return 값은 상태값이다.

 

class Solution:
    
    longest=0
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node:TreeNode):
            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