[LeetCode] 1448. Count Good Nodes in Binary Tree

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

Count Good Nodes in Binary Tree - LeetCode

Count Good Nodes in Binary Tree.

 

 

 

노드의 value가 모든 조상 노드의 value들보다 작지 않은 경우가 몇가지인지를 묻는 문제이다.

즉, 조상 노드의 최대값 <= 현재 노드인 노드의 개수를 구하면 된다.

 

이 문제는 hint가 있길래 무심코 눌렀다가 크게 스포를 당해버려 매우 쉬워져버렸다.

역시 바로 풀게되어 악필 풀이가 없다.

 

해법은 DFS와 최대값을 이용하면 된다.

DFS로 root부터 모든 노드를 훑으며, 해당 노드가 최대값보다 크거나 같다면 결과를 ++ 해주면 된다.

 

먼저 DFS 코드다.

DFS 메소드는 가리킬 노드와 훑어온 노드들의 최대값을 받아 sum이라는 int 형 변수를 리턴하도록 한다.

sum은 0으로 세팅된다.

현재 노드의 값을 받아온 최대값과 비교하여 현재 노드값이 최대값보다 크거나 같다면 sum++을 해주고 M을 현재 노드값으로 바꿔준다.

 

그 후, 왼쪽, 오른쪽 자식 노드들을 다시 DFS에 넣어 나온 값을 각각 더해주면 된다.

 

int DFS(TreeNode* node, int M) {
    int sum = 0;
    if (M<=node->val) {
        M = node->val;
        sum++;
    }
    if (node->left!=NULL) sum += DFS(node->left, M);
    if (node->right!=NULL) sum += DFS(node->right, M);
    return sum;
}

 

메인 코드는 DFS에 root와 초기 최대값(=-98765, 문제에서 노드의 최소값이 -10000 이므로.)을 넣어 리턴해주면 된다.

 

int goodNodes(TreeNode* root) {
    return DFS(root, -98765);
}

 

전체 코드는 아래와 같다.

 

class Solution {
public:
    int DFS(TreeNode* node, int M) {
        int sum = 0;
        if (M<=node->val) {
            M = node->val;
            sum++;
        }
        if (node->left!=NULL) sum += DFS(node->left, M);
        if (node->right!=NULL) sum += DFS(node->right, M);
        return sum;
    }
    
    
    int goodNodes(TreeNode* root) {
        return DFS(root, -98765);
    }
};