[1스4코2파] # 209 LeetCode 1448. Count Good Nodes in Binary Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (209차)
[4코1파] 2023.01.13~ (201일차)
[1스4코1파] 2023.04.12~ (112일차)
[1스4코2파] 2023.05.03 ~ (90일차)

Today :

2023.08.01 [210일차]
Tree
1448. Count Good Nodes in Binary Tree

1448. Count Good Nodes in Binary Tree

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

문제 설명

binary tree가 주어졌을 때, 트리의 root 노드에서 다음 노드까지의 경로가 root 노드의 값보다 큰 값을 가지면 good node인데, good node의 수를 return 한다.

문제 풀이 방법

dfs를 이용해서 tree를 탐색하는데, MaxVal의 값을 root 값과 max로 비교해서 maxVal를 바꿔줘야 한다. 그 이하는 node의 left, right를 넣어주면서 탐색하는 것과 유사함

내 코드

 class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:

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

            ans = 1 if node.val >= maxVal else 0
            maxVal = max(maxVal, node.val)
            ans += dfs(node.left, maxVal)
            ans += dfs(node.right, maxVal)

            return ans

증빙

여담

아침댓바람부터 나무심기 완료