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,,
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 ~
CodePudding user response：
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.
CodePudding user response：
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
