[LeetCode 해석 및 풀이] 1448. Count Good Nodes in Binary Tree(이진 트리에서 좋은 노드 계산)

LeetCode 문제 해석 및 풀이 방법

문제 1448. Count Good Nodes in Binary Tree(이진 트리에서 좋 노드 계산)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

 

Return the number of good nodes in the binary tree.

 

한글

이진 트리 root 주어질 때, 루트에서 X 까지의 경로에 X 보다 큰 값을 가진 노드가 없으면 트리의 노드 X 는 good 으로 명명됩니다.

 

이진 트리의 좋은 노드 수를 반환합니다.

 

제한조건

• The number of nodes in the binary tree is in the range [1, 10^5].
• Each node's value is between [-10^4, 10^4].

 

입출력 예

입력	출력
root = [3,1,4,3,null,1,5]	4
root = [3,3,null,4,2]	3
root = [1]	1

 

해답 및 해설

파이썬 (Python)

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        good_count = 0

        def maxNumCheckDFS(node, max_num):
            if not node:
                return
            
            nonlocal good_count

            if max_num is None or node.val >= max_num:
                good_count += 1
                max_num = node.val
            
            maxNumCheckDFS(node.left, max_num)
            maxNumCheckDFS(node.right, max_num)
        
        maxNumCheckDFS(root, None)
    
        return good_count

 

102. Binary Tree Level Order Traversal 문제에서 깊이 우선 탐색으로 풀던 방식과 똑같이 풀되, 넘겨주는 값을 이전까지 경로에서 중 가장 큰 값으로 둔다. 같거나 더 큰 값이 생기면 최대값을 해당값으로 바꾸고 좋은 노드라고 체크한다.