Tree: 1448. Count Good Nodes in Binary Tree

1448. Count Good Nodes in Binary Tree

 

https://youtu.be/7cp5imvDzl4?si=6kO3CQDgpb403ogg

 

# 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 goodNodes(self, root: TreeNode) -> int:
        
        def dfs(node, maxVal):
            """
            dfs 함수는 재귀적으로 트리를 탐색하며 "좋은 노드"를 계산함
            """
            # 노드가 None인 경우, 탐색을 종료하고 0을 반환.
            # 예: 리프 노드에서 왼쪽 또는 오른쪽 자식이 없는 경우.
            if not node: 
                return 0
            
            # 현재노드가 좋은 노드인지 아닌지 
            res = 1 if node.val >= maxVal else 0 # 0 이면 not good node
            
            # 경로 최대값 갱신:
			# 현재 노드의 값과 기존 최대값 중 더 큰 값을 선택해 maxVal을 업데이트.
			# 이 값은 이후의 자식 노드에서 "좋은 노드"인지 판단할 기준이 됨
            maxVal = max(maxVal, node.val)

			# 왼쪽 및 오른쪽 서브트리를 탐색하여,
			# 왼쪽과 오른쪽에서 반환된 "좋은 노드"의 개수를 res에 추가.
            res += dfs(node.left, maxVal)
            res += dfs(node.right, maxVal)
            
            # 현재 노드를 포함한 "좋은 노드"의 개수를 반환.
            return res

		# 처음 호출할 때: (루트 노드, 루트 노드의 값, 즉, 현재 경로의 최대값) 으로 초기화
        return dfs(root, root.val)

 

이제 그냥 품

# root 에서 어떤 노드까지 가는데 어떤 노드값보다 큰값이 없으면, 그 어떤 노드는 good 노드가 됨

# 즉, Good Node란, 루트에서 해당 노드까지의 경로에서 그 노드의 값이 최대값이라면 그 노드는 Good Node

 

# 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 goodNodes(self, root: TreeNode) -> int:
        # root 에서 어떤 노드까지 가는데 어떤 노드값보다 큰값이 없으면, 그 어떤 노드는 good 노드가 됨
        # 즉, Good Node란, 루트에서 해당 노드까지의 경로에서 그 노드의 값이 최대값이라면 그 노드는 Good Node
        if not root:
            return 0

        res = [0]

        def dfs(node, max_val):
            if node.val >= max_val:
                res[0] +=1
                max_val = node.val

            if node.left:
                dfs(node.left, max_val)
            if node.right:
                dfs(node.right, max_val)

        dfs(root, root.val)
        return res[0]