[리트코드(LeetCode)] 543번 Diameter of Binary Tree

문제

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

Diameter of Binary Tree - LeetCode

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

예시

Example 1:

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].

 

Example 2:

Input: root = [1,2]
Output: 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: 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

 

- 주어진 이진 트리의 루트 노드를 받아 dfs를 활용하여 각 노드를 방문하면서 가장 긴 경로를 반환한다.

- 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리에 대한 높이 정보를 얻어오고, 가장 긴 경로를 업데이트한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview