2049 Count node with highest score

2049CountNodesWithHighestScore

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _2049_count_nodes_with_the_highest_score
{
    class Solution
    {
        static void Main(string[] args)
        {
            var test = new Solution();

            var result1 = test.CountHighestScoreNodes(new int[]{-1});  // 1
            var result2 = test.CountHighestScoreNodes(new int[]{-1,0}); // maxScore = 1, but number of nodes is 2; two cases, remove 0, remove 1
            var result3 = test.CountHighestScoreNodes(new int[]{-1, 0, 0}); // maxScore = 2, and number of nodes is 2

            var result4 = test.CountHighestScoreNodes(new int[]{-1, 2, 0, 2, 0}); 
        }

        /// <summary>
        /// 
        /// </summary>
        Dictionary<int, int[]> children = new Dictionary<int, int[]>();
        long maxScore = 0;
        int  numberNodes = 0;

        /// <summary>
        /// Oct. 30, 2023
        /// Study code
        /// https://leetcode.com/problems/count-nodes-with-the-highest-score/solutions/3983979/c-dfs-solution/
        /// </summary>
        /// <param name="parents"></param>
        /// <returns></returns>
        public int CountHighestScoreNodes(int[] parents)
        {
            int n = parents.Length;
            var lstParents = new List<int>(parents);

            // build a graph based on parents - left or right child - does not matter
            for (int i = 0; i < parents.Length; i++)
            {
                var childNodes = new int[] { -1, -1 };

                // two children
                // 
                var parentNode = parents[i];

                if (children.ContainsKey(parentNode))
                {
                    children[parentNode][1] = i;
                }
                else
                {
                    childNodes[0] = i;
                    children.Add(parentNode, childNodes);
                }
            }

            // Extra - no children 
            // Leaf node 
            for (int i = 0; i < parents.Length; i++)
            {
                var arr = new int[] { -1, -1 };

                if (!children.ContainsKey(i))
                {
                    children.Add(i, arr);
                }
            }

            // Binary tree rooted at 0 - start from root node
            countNodesDFS(0, n);
            return numberNodes;
        }

        /// <summary>   
        /// Return number of nodes that have the highest score
        /// node's value from 0 to n - 1
        /// </summary>
        /// <param name="root"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        private long countNodesDFS(int root, int n)
        {
            long score = 0;
            long subtreeCount = 0;

            if (root == -1)
            {
                return 0;
            }

            long leftCount = countNodesDFS(children[root][0], n);
            long rightCount = countNodesDFS(children[root][1], n);

            subtreeCount = leftCount + rightCount + 1;
            long remain = n - subtreeCount;
            
            score = (leftCount == 0 ? 1 : leftCount) * (rightCount == 0 ? 1 : rightCount);
            score *= remain == 0 ? 1 : remain;

            if (score > maxScore)
            {
                maxScore = score;
                numberNodes = 1;
            }
            else if (score == maxScore)
            {
                numberNodes++;
            }

            return subtreeCount;
        }        
    }
}