[LeetCode 해석 및 풀이] 543. Diameter of Binary Tree (이진 트리에서의 지름)

LeetCode 문제 해석 및 풀이 방법

 

문제 543. Diameter of Binary Tree (이진트리에서의 지름)

바로가기

 

문제 설명

영문

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

 

한글

이진트리의 root가 주어지면, 이진트리에서의 지름을 반환하시오.

 

이진트리의 지름이란 트리에서 두 노드간의 가장 긴 경로의 길이를 뜻합니다. 이 경로는 root를 통과할수도, 안 할수도 있습니다.

 

두 노드간의 경로의 길이는 두 노드 사이의 간선 수로 나타내니다.

 

제한조건

• The number of nodes in the tree is in the range [1, 10^4].
• -100 <= Node.val <= 100

 

입출력 예

입력	출력
[1,2,3,4,5]	3
[1,2]	1

 

 

해답 및 해설

파이썬 (Python)

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def treeDepthDiameter(head):
            if not head:
                return (0, 0)
            
            left_depth, left_diameter = treeDepthDiameter(head.left)
            right_depth, right_diameter = treeDepthDiameter(head.right)

            depth = max(left_depth, right_depth) + 1
            diameter = max(left_diameter, right_diameter, left_depth + right_depth)

            return (depth, diameter)
        
        _, diameter = treeDepthDiameter(root)

        return diameter

 

이진 트리의 최대 깊이를 구할 때처럼 재귀를 이용하여 하위트리에서 지름, 깊이를 구한다음, 왼쪽, 오른쪽 깊이를 더한 값과 이전 최대 깊이를 비교해 반환하는 방식을 이용하였다.

 

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        max_diameter = 0

        def treeDepthDiameter(head):
            nonlocal max_diameter

            if not head:
                return 0
            
            left_depth = treeDepthDiameter(head.left)
            right_depth = treeDepthDiameter(head.right)

            depth = max(left_depth, right_depth) + 1
            max_diameter = max(max_diameter, left_depth + right_depth)

            return depth

        treeDepthDiameter(root)

        return max_diameter

다음과 같이 전역변수를 이용하는 방법도 있다. 어차피 지름은 최대값만 필요하기 때문이다.