[알고리즘][트리] - 2. 이진 트리의 직경

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

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

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

---

[상태값 누적 트리 DFS]

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