← 전체 회차
A-055● Day 552026.07.01mediumleetcode #1448neetcode150

이진 트리의 좋은 노드 개수 세기

#tree#depth-first-search#breadth-first-search#binary-tree
↗ leetcode #1448 · count-good-nodes-in-binary-tree
01

문제

· problem
P.055

이진 트리의 좋은 노드 개수 세기

↗ leetcode #1448

이진 트리 root가 주어진다. 트리의 노드 X는 root에서 X까지의 경로에서 X보다 큰 값을 가진 노드가 없으면 "좋은" 노드라고 한다. 이진 트리의 좋은 노드의 개수를 반환하시오.

제약
  • · 1 ≤ number of nodes ≤ 10^5
  • · -10^4 ≤ node value ≤ 10^4
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,1,4,3,null,1,5]
4
example 2input → output
[3,3,null,4,2]
3
example 3input → output
[1]
1
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    루트 노드는 항상 좋은 노드인가?
  • ☐
    노드 값이 음수일 수 있는가?
  • ☐
    "루트에서 X까지의 경로"에 현재 노드 X가 포함되는가?
  • ☐
    모든 노드의 값이 같을 경우, 모두 좋은 노드인가?
  • ☐
    경로는 항상 루트에서 시작해야 하는가?
  • ☐
    트리가 비어있을 경우를 처리해야 하는가?
  • ☐
    트리 구조를 수정할 수 있는가?
  • ☐
    좋은 노드들 자체를 반환해야 하는가?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 재귀 기저 사례: 노드 존재 여부 확인
○
if not node:
○
if node is None:
○
if node == None:
step 2· 현재 노드가 좋은 노드인지 판단│ 중첩
○
res = 1 if node.val >= maxVal else 0
○
res = 1 if node.val > maxVal else 0
○
res = 1 if node.val <= maxVal else 0
step 3· 경로상 최대값 업데이트│ 중첩
○
maxVal = max(maxVal, node.val)
○
maxVal = node.val
○
maxVal = min(maxVal, node.val)
step 4· 왼쪽 서브트리 순회 및 개수 누적│ 중첩
○
res += dfs(node.left, maxVal)
○
res += dfs(node.left, node.val)
○
dfs(node.left, maxVal)
step 5· 오른쪽 서브트리 순회 및 개수 누적│ 중첩
○
res += dfs(node.right, maxVal)
○
res = dfs(node.right, maxVal)
○
res += dfs(node.right, node.val)
step 6· 누적된 개수 반환│ 중첩
○
return res
○
return 1
○
return res + 1
step 7· 초기 호출: 루트에서 DFS 시작
○
return dfs(root, root.val)
○
return dfs(root, float('-inf'))
○
return dfs(root, 0)
각 슬롯에 한 줄씩 골라보세요
// 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 goodNodes(self, root: TreeNode) -> int:
9
        def dfs(node, maxVal):
10
            if not node:
11
                return 0
12
13
            res = 1 if node.val >= maxVal else 0
14
            maxVal = max(maxVal, node.val)
15
            res += dfs(node.left, maxVal)
16
            res += dfs(node.right, maxVal)
17
            return res
18
19
        return dfs(root, root.val)
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,1,4,3,null,1,5]
→
4
case 2
[3,3,null,4,2]
→
3
case 3
[1]
→
1
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.