[Binary Tree][DFS] 1448. Count Good Nodes in Binary Tree

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

Count Good Nodes in Binary Tree - LeetCode

 

 

Q. 주어진 tree에서 root와 특정 노드 x 사이에서, 과정을 포함한 모든 노드에서 x노드 값보다 큰 값이 없으면, 해당 노드를 good node라 한다. 해당 tree에서 good node의 수를 반환하라.

 

Solution. 

 root와 특정 노드까지의 과정을 check해야 하므로, DFS를 사용해야 함을 알수 있다.

 단순히 생각해 볼때, 이 과정을 모든 노드에 대해서 처리하면 될 것 같다. 

 

좌측 1 노드까지 가서 root인 3과 1 확인, - not good

좌측 제일 하단 3 노드까지 가서 3, 1, 3 확인 - good 

다른 쪽 사이드 3, 1, 5 도 마찬 가지... 

 

모든 노드를 순회하면서 역시 tree의 depth만큼 자료를 저장하고 다시 조회한다. O(N x depth) 

뭔가 최적화 되지 않은 느낌이다. 

 

다시 조금 더 생각해 보자. 

특정 노드 1까지 갔을때, 1과 비교하고자 하는 값은 무엇인가, 과연 모든 지나온 노드 값이 다 필요한가 를 다시 생각해보면 그렇지 않다는 것을 알 수 있다. 

결국 필요한 것은 대상 노드와 비교할 과정중의 최대값인 것을 알 수 있다. 따라서 지나쳐온 모든 노드의 정보를 기억해 둘 필요 없이 최대값만 비교해서 같거나 작으면, 대상 노드는 good node이다. 

 

void goodNodes_Helper(TreeNode* node, int &count, int maxV)
{
    if (node == NULL)	return;

    if (node->val >= maxV)
        ++count;

    maxV = max(maxV, node->val);

    if (node->left != NULL)		goodNodes_Helper(node->left, count, maxV);
    if (node->right != NULL)	goodNodes_Helper(node->right, count, maxV);
}
int goodNodes(TreeNode* root)
{
    int ret = 0, max = INT_MIN;
    goodNodes_Helper(root, ret, max);
    return ret;
}