← 전체 회차
A-048● Day 482026.06.23easyleetcode #543neetcode150

이진 트리의 지름

#tree#depth-first-search#binary-tree
↗ leetcode #543 · diameter-of-binary-tree
01

문제

· problem
P.048

이진 트리의 지름

↗ leetcode #543

이진 트리의 루트가 주어졌을 때, 트리의 지름의 길이를 반환하세요. 이진 트리의 지름은 트리의 임의의 두 노드 사이의 가장 긴 경로의 길이입니다. 이 경로는 루트를 지날 수도 있고 지나지 않을 수도 있습니다. 두 노드 사이 경로의 길이는 그 사이의 간선(edge)의 개수로 표현됩니다.

제약
  • · The number of nodes in the tree is in the range [1, 10^4]
  • · -100 ≤ Node.val ≤ 100
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,2,3,4,5]
3
example 2input → output
[1,2]
1
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    지름 경로는 반드시 루트를 지나야 하나요?
  • ☐
    경로의 길이는 노드 개수로 세나요, 간선 개수로 세나요?
  • ☐
    노드가 1개인 트리의 지름은 얼마인가요?
  • ☐
    DFS 재귀에서 각 노드가 반환해야 할 값은 무엇인가요?
  • ☐
    지름의 최댓값은 각 노드에서 어떻게 계산되나요?
  • ☐
    시간 복잡도를 O(1)로 개선할 수 있나요?
  • ☐
    지름이 트리의 높이와 같을 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 결과 변수 초기화
○
res = 0
○
res = -1
○
res = float('inf')
step 2· DFS 함수 정의
○
def dfs(root):
○
def bfs(root):
○
def diameter(root):
step 3· 재귀 종료 조건│ 중첩
○
if not root:
○
if root is None: return -1
○
if not root.left and not root.right: return 1
step 4· 왼쪽/오른쪽 자식 높이 계산│ 중첩
○
left = dfs(root.left)
○
left = dfs(root.left) + 1
○
right = root.right.val
step 5· 지름 최댓값 갱신│ 중첩
○
res = max(res, left + right)
○
res = left + right
○
res += left + right
step 6· 현재 노드의 높이 반환│ 중첩
○
return 1 + max(left, right)
○
return max(left, right)
○
return left + right
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
9
        res = 0
10
11
        def dfs(root):
12
            nonlocal res
13
14
            if not root:
15
                return 0
16
            left = dfs(root.left)
17
            right = dfs(root.right)
18
            res = max(res, left + right)
19
20
            return 1 + max(left, right)
21
22
        dfs(root)
23
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,2,3,4,5]
→
3
case 2
[1,2]
→
1
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.