[leetcode] 1448. Count Good Nodes in Binary Tree 파이썬 코드

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

 

이 문제가 2021년 마이크로소프트 코테에서 최다 빈출 문제였었다고 한다. 

 

goodnode라는 건 root로부터 시작해서 특정 위치까지 왔을 때 자기보다 큰 노드가 없다면 그 노드를 good node로 정의할 것이다. preorder 순회를 하는데 이전 노드들의 최대값과 현재 노드값을 비교해서 만약에 현재 노드가 크다면, good node이므로 +1을 해준다.

 

class Solution(object):
    def goodNodes(self, root):
        
        def dfs(root, max_value):
            if not root:
                return 0
            
            result = 1 if root.val >= max_value else 0
            max_value = max(max_value, root.val)

            result += dfs(root.left, max_value)
            result += dfs(root.right, max_value)
            return result

        return dfs(root, float("-inf"))