[DSA][Trees] 10. Count Good Nodes in Binary Tree

LeetCode 1448

 

10. 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.

 

 

[질문하기]

- 경로상 최댓값과 현재 노드의 값이 같은 경우에도 good node인가요?

- 노드 값은 양수인가요? NO

 

[아이디어]

- 재귀 함수를 사용하여 현재 노드와 maxVal을 비교하여 카운트한다.

 

 

[풀이 1] Depth First Search

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, maxVal):
            if not node:
                return 0

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

        return dfs(root, root.val)

자식 노드로 재귀적으로 타고 내려가면서, 그때까지의 maxVal과 비교해서 현재 노드의 값이 더 크거나 같으면 카운트하고, 아니면 pass 한다. 그 후에 왼쪽, 오른쪽 자식에서 돌아온 결과들을 더해서 리턴하면 된다.

 

⏱️ 시간복잡도

트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되기 때문에 O(h)에 비례하고 따라서 공간 복잡도는 최악의 경우 O(N) (Skew 트리)이고, 평균적으로는 O(log N) (균형 잡힌 트리)이다.