[LeetCode] 1448. Count Good Nodes in Binary Tree (C#)

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

 

Root 노드부터 현재 노드(X)까지 이동하는 동안 자신(X)보다 큰 값을 가진 노드가 없는 경우 X는 GoodNode가 된다.

이때 주어진 이진 트리의 GoodNode 개수를 구하는 문제.

 

 

1. 풀이

• 현재 노드의 값이 지금까지 지나온 값들과 비교해 같거나 크면 GoodNode 카운팅

namespace PS.LeetCode;

public class Solution_1448_1
{
    public int GoodNodes(TreeNode root)
    {
        var result = 0;
        Dfs(root, root.val, ref result);

        return result;
    }

    void Dfs(TreeNode cur, int largestVal, ref int goodCnt)
    {
        if (cur == null)
        {
            return;
        }

        if (cur.val >= largestVal)
        {
            goodCnt++;
        }

        largestVal = Math.Max(largestVal, cur.val);
        
        Dfs(cur.left, largestVal, ref goodCnt);
        Dfs(cur.right, largestVal, ref goodCnt);
    }
}