[LeetCode] 1448 | Count Good Nodes in Binary Tree | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

• 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].

---

내 풀이

Tree 구조는 항상 recursive하게 짠다는 생각을 베이스로 시작한다.

이전 노드까지의 최댓값을 prev_max에 저장한다.

현재 root값이 prev_max보다 크거나 같으면 문제에서 말하는 조건에 해당하기 때문에 ans+=1로 해주고, prev_max의 값을 갱신한다.

갱신된 prev_max값으로 다시 root.left, root.right에 recursive하게 동작하도록 한다.

---

코드

# 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:
        ans = 0
        
        def search(root, prev_max):
            nonlocal ans
            if not root:
                return
            
            if root.val >= prev_max:
                ans += 1
                prev_max = root.val
            
            search(root.left, prev_max)
            search(root.right, prev_max)
            
        search(root, root.val)
        
        return ans