[LeetCode] Diameter of Binary Tree (이진트리 가장 긴 경로)

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

Diameter of Binary Tree - LeetCode

 

class Solution:
    longest: int = 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

왼쪽 리프 노드까지의 길이와 오른쪽 리프 노드까지의 길이를 찾고

매 서브트리마다 재귀적으로 찾아서 클래스 변수 logest를 수정해주면 된다.

 

longest를 클래스 변수로 둔 이유는 immutable 객체를 중첩 함수에서 재할당하려고 하면 로컬 변수로 새로 생성되기 때문이다.

muutable 객체는 수정 가능