[BinaryTree][Medium] 1448. Count Good Nodes in Binary Tree

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

 

주어진 Binary Tree에서 good node의 수를 찾아라. 

good node는 root와 해당 노드 사이에 자신보다 큰 수가 없어야 한다.

 

특정 노드를 기준으로 root와 자신 사이에 max value를 구한다. 

이 값이 node->val 보다 같거나 작으면 조건을 만족하는 것이다. 

 

노드의 중복 탐색을 피하기 위해 자신을 포함하여 max value를 재 계산하고 

다시 child로 내려가 조건 검사를 이어 간다. 

 

코드 

void goodNodesHelper(int& cnt, int maxV, TreeNode* node)
{
    if (node == nullptr)
        return;

    if (node->val >= maxV)
    {
        ++cnt;
        maxV = node->val;
    }

    goodNodesHelper(cnt, maxV, node->left);
    goodNodesHelper(cnt, maxV, node->right);
}

int goodNodes(TreeNode* root) 
{
    if (root == nullptr)
        return 0;

    int cnt = 0;
    goodNodesHelper(cnt, root->val, root);
    return cnt;
}

 

 

결과