greentea31's Note

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

풀이 과정

이진 트리의 지름, 즉 이진 트리의 노드들 사이의 가장 긴 경로를 구하는 문제이다.

이진 트리의 지름은 루트 노드와 리프 노드 사이의 거리이거나, 리프 노드와 리프 노드 사이의 거리이다. 루프 노트와 리프 노드의 사이의 거리는 트리의 높이를 구하면 해결할 수 있는 문제이지만 리프 노드와 리프 노드 사이의 거리는 어떻게 문제를 해결할 것인가?

DFS로 각 노드들에 리프노드와의 거리를 상태값으로 부여하자. 그러면 특정 노드를 루트로 하는 트리의 Diameter는 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2가 된다.

이 모든 과정을 마쳤을 때, 루트 노드에 대해서 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2를 더해주면 전체 트리의 지름을 구할 수 있다. 

자식 노드가 없는 경우에는 그 자식 노드의 상태값을 -1로 가정하고 계산을 진행해주어야 트리의 지름을 정상적으로 구할 수 있다.

소스 코드

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