Leetcode #2265 , I implement this with c#, but I find that one test case output seems to be incorrect, don't know why

Question

I try to take the challenge of this leetcode problem : https://leetcode.com/problems/count-nodes-equal-to-average-of-subtree

And this is my solution :

    public class Solution {
     public  int AverageOfSubtree(TreeNode root)
        {
            int sumOfNodes = 0;
            if (root.left == null && root.right == null)
            {
                sumOfNodes = 1;
                return sumOfNodes;
            }
            sumOfNodes = 0;
            Dictionary<int, bool> addedNodes = new Dictionary<int, bool>();
            
            Func<TreeNode, Tuple<int[], int>> FindNodes = null;
            FindNodes = (rt) => {
                if (rt.left == null && rt.right == null)
                {
                    sumOfNodes += 1;
                    addedNodes[rt.val] = true;
                    return new Tuple<int[], int>(new int[] { rt.val }, rt.val);
                }
                Tuple<int[], int> leftResult = null;
                Tuple<int[], int> rightResult = null;
                List<int> subTreeList = new List<int>();

                if (rt.left != null)
                {
                    leftResult = FindNodes(rt.left);
                }
                else
                {
                    leftResult = new Tuple<int[], int>(new int[] { }, 0);
                }
                if (rt.right != null)
                {
                    rightResult = FindNodes(rt.right);
                }
                else
                {
                    rightResult = new Tuple<int[], int>(new int[] { }, 0);
                }
                int average = (leftResult.Item2 + rightResult.Item2 + rt.val) / (leftResult.Item1.Length + rightResult.Item1.Length + 1);
                foreach (var leftNode in leftResult.Item1)
                {

                    if (average == leftNode)
                    {
                        if (!addedNodes.ContainsKey(leftNode))
                        {
                            sumOfNodes += 1;
                            addedNodes[leftNode] = true;
                        }
                    }
                    if (!subTreeList.Contains(leftNode))
                    {
                        subTreeList.Add(leftNode);
                    }
                }
                foreach (var rightNode in rightResult.Item1)
                {

                    if (average == rightNode)
                    {
                        if (!addedNodes.ContainsKey(rightNode))
                        {
                            sumOfNodes += 1;
                            addedNodes[rightNode] = true;
                        }
                    }
                    if (!subTreeList.Contains(rightNode))
                    {
                        subTreeList.Add(rightNode);
                    }
                }
                if (rt.val == average)
                {
                    sumOfNodes += 1;
                }
                subTreeList.Add(rt.val);
                return new Tuple<int[], int>(subTreeList.ToArray(), (leftResult.Item2 + rightResult.Item2 + rt.val));
            };
            FindNodes(root);
            return sumOfNodes;
        }
}

Which can pass the test case examples , but after I submit the code, I got the wrong answer from the figure below,,

wrong answer

don't know why the result is 2 rather than 3 , according to the problem's description, the possible nodes of the case in figure should be :

leaf nodes => 3,4 and also 2 , because (0+4+2+3+4)/5 = 2.6 , which round down to 2

so should be 3 rather than 2...

Can somebody tell why this is the answer ?? Do I misunderstand something ? Thank you ~

Looks like they are doing integer division which just truncates the remainder. In C# you do this by using "\" instead "/". — B.O.B., May 09 '22 at 05:13
The TreeNode class is defined as : public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { this.val = val; this.left = left; this.right = right; } } — timmony0509, May 09 '22 at 05:14
Hi @B.O.B. , thank you for the response, but.. I don't quite understand what you mean,, because in c#, the division operator is "/" rather than "\", and I think the problem may not happen there... — timmony0509, May 09 '22 at 05:20
Doh. Thinking of a different language. Disregard the \ vs /. When dealing with integers in C# it automatically deals with truncating. — B.O.B., May 09 '22 at 05:20
https://stackoverflow.com/questions/10851273/why-does-integer-division-in-c-sharp-return-an-integer-and-not-a-float <- this should prove informative. — B.O.B., May 09 '22 at 05:21
@B.O.B. I think the truncate here is okay because the problem requires the result of division to be round down, so the round part is needed to be ignored, which just as the truncate does ~ — timmony0509, May 09 '22 at 05:27

score 0 · Answer 1 · answered May 09 '22 at 05:27

0


    0: (0+4+2+3+4)/5 = 2.6 => 2 != 0
    4: (4+3)/2 = 3.5 => 3 != 4
    2: (2+4)/2 = 3 != 2
    3: 3/1 = 3 == 3
    4: 4/1 = 4 == 4

Looks like the result should be 2 to me.

answered May 09 '22 at 05:27

John

3,057
1
4
10

Got it ! So that means checking if "root node number" matches the average , not all nodes that match the average – timmony0509 May 09 '22 at 05:33

score 0 · Answer 2 · answered May 09 '22 at 06:01

Thank you all, I think that I misundersand the meaning of what the problem asks, and after I fix my code and submit , it is accepted !!

What I fix is to remove the double check of average for nodes that aren't root node and also the duplicate value 's check for subtree nodes

My fixed code is as follows:

public  int AverageOfSubtree(TreeNode root)
        {
            int sumOfNodes = 0;
            if (root.left == null && root.right == null)
            {
                sumOfNodes = 1;
                return sumOfNodes;
            }
            sumOfNodes = 0;
            Dictionary<int, bool> addedNodes = new Dictionary<int, bool>();
            
            Func<TreeNode, Tuple<int[], int>> FindNodes = null;
            FindNodes = (rt) => {
                if (rt.left == null && rt.right == null)
                {
                    sumOfNodes += 1;
                    addedNodes[rt.val] = true;
                    return new Tuple<int[], int>(new int[] { rt.val }, rt.val);
                }
                Tuple<int[], int> leftResult = null;
                Tuple<int[], int> rightResult = null;
                List<int> subTreeList = new List<int>();

                if (rt.left != null)
                {
                    leftResult = FindNodes(rt.left);
                }
                else
                {
                    leftResult = new Tuple<int[], int>(new int[] { }, 0);
                }
                if (rt.right != null)
                {
                    rightResult = FindNodes(rt.right);
                }
                else
                {
                    rightResult = new Tuple<int[], int>(new int[] { }, 0);
                }
                int average = (leftResult.Item2 + rightResult.Item2 + rt.val)/ (leftResult.Item1.Length + rightResult.Item1.Length + 1);
                foreach (var leftNode in leftResult.Item1)
                {
                    subTreeList.Add(leftNode);
                }
                foreach (var rightNode in rightResult.Item1)
                {
                    subTreeList.Add(rightNode);
                }
                if (rt.val == average)
                {
                    sumOfNodes += 1;
                }
                subTreeList.Add(rt.val);
                return new Tuple<int[], int>(subTreeList.ToArray(), (leftResult.Item2 + rightResult.Item2 + rt.val));
            };
            FindNodes(root);
            return sumOfNodes;
        }

accepted result: accepted result

Leetcode #2265 , I implement this with c#, but I find that one test case output seems to be incorrect, don't know why

2 Answers2