[Leetcode] 543. Diameter of Binary Tree_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '543. Diameter of Binary Tree'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Diameter of Binary Tree' 알고리즘 문제

 

STEP 2. 'Diameter of Binary Tree' 코드(code)

 

STEP 3. 'Diameter of Binary Tree' 해설

 

STEP 4. 'Diameter of Binary Tree' solution

 

반응형

 

STEP 1. '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.

 

이진트리의 루트가 주어졌을 때, 트리의 지름(diameter)의 길이를 반환하시오.
이진트리의 지름은 트리 내의 두 노드 사이의 가장 긴 경로를 의미하며, 이 경로는 루트를 지나갈 수도 있고, 지나가지 않을 수도 있습니다. 경로의 길이는 두 노드 사이의 간선(edge) 개수로 측정됩니다.

 

Constraints:

 

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

 

---

STEP 2. 'Diameter of Binary Tree' 코드(code)

 

■ Runtime: 3ms Beats 93.73%
■ Memory: 20.93MB Beats 21.26%

 

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

        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            right= dfs(node.right)

            self.max_diameter = max(left+right, self.max_diameter)

            return 1 + max(left, right)

        dfs(root)
        return self.max_diameter

---

STEP 3. 'Diameter of Binary Tree' 해설

 

노드의 최대 깊이 (depth)와 이를 바탕으로, 최대 지름을 계산해야 합니다. 재귀 함수를 통해서 깊이를 계산하면서 self.max_diameter를 통해서 이전에 연산한 왼쪽 노드와 오른쪽 노드의 최대 지름과 현재 지름을 비교해야 합니다.

 

max(left+right, self.max_diameter)를 통해서 현재 값과 과거 값을 비교할 수 있습니다.

 

 

STEP 4. 'Diameter of Binary Tree' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다. 이전 최대 지름의 길이와 비교해야 하기에, nonlocal, global 변수로 res를 만들어서 계산했습니다.

 

■ Runtime: 7ms Beats 46.51%
■ Memory: 20.89MB Beats 48.42%

 

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

        def dfs(root):
            if not root:
                return 0
            
            l = dfs(root.left)
            r = dfs(root.right)

            nonlocal res
            res = max(res, l + r)

            return 1 + max(l, r)

        dfs(root)
        return res

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '543. Diameter of Binary Tree'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.