LeetCode - Count Good Nodes in Binary Tree - swift

https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/615/week-3-august-15th-august-21st/3899/

 

문제는 Good 이라는 노드의 개수를 찾는 것인데,

Good 노드인 경우는, root노드로부터 x노드까지 가는 경로에 x노드보다 큰 값이 없는 경우에 Good 노드라고 한다. 

노드의 개수는 최대 10만개이다. 

 

간단한 이진트리를 탐색하는 문제다.

자식노드들이 Good노드이냐 아니냐만 판별하여 카운팅하면 된다.

모든 노드들을 방문하므로, O(N)이 걸린다. 

그러므로, 매번 자식노드들을 탐색할때, 지금까지 방문한 노드들의 값의 최대값을 저장하면서 현재 노드와 값을 비교하면 된다.

 

class Solution {
    func goodNodes(_ root: TreeNode?) -> Int {
        var ans = 0
        
        func find(node: TreeNode?, mx: Int ) {
            if node == nil { return }
            let nextMax = max(node!.val, mx)
            if node!.val >= nextMax {
                ans += 1
            }
            find(node: node?.left, mx: nextMax)
            find(node: node?.right, mx: nextMax)
        }
        find(node: root, mx: -10000)
        return ans
    }
}