给定一个节点,如
class Node
{
public int Val { get; set; }
public Node Parent { get; set; }
public List<Node> Children { get; set; } = new List<Node>();
/// <summary>
/// Sum of values in descendant nodes
/// </summary>
public int DescendantsSum { get; set; } = 0;
/// <summary>
/// Sum of values in tree whose root is this node
/// </summary>
public int TreeSum { get { return Val + DescendantsSum; } }
}
和Node
s与Val
s的树已经设置,我要做的是下面我写的方法的总结中所描述的
/// <summary>
/// Given a tree like
///
/// Val=100
///
/// Val=200
/// /
/// / Val=100
/// Val=100
/// /
/// Val=500 Val=600
///
/// set a field for each node showing the sum of the values
/// in the subtree whose root is that node, making it into
///
/// Val=100
/// Sum=1600
///
/// Val=200
/// Sum=1500
/// /
/// / Val=100
/// / Sum=100
/// Val=100
/// Sum=1200
/// /
/// Val=500 Val=600
/// Sum=500 Sum=600
///
/// </summary>
static void SetSums(Node[] nodes)
{
foreach(var leaf in nodes.Where(node => node.Children.Count == 0))
for(var cur = leaf; cur.Parent != null; cur = cur.Parent)
cur.Parent.DescendantsSum += cur.TreeSum;
}
然而,这会导致不正确的大值,如3400
,它应该是1600
。我仔细考虑过我的算法,我看不出哪里有缺陷。有提示吗?
当你在处理树时,有时从上到下更容易,而不是像你那样从上到下。
我想这应该能满足你的需要:
public class Node
{
public int Val { get; set; }
public Node Parent { get; set; }
public List<Node> Children { get; set; } = new List<Node>();
/// <summary>
/// Sum of values in descendant nodes
/// </summary>
public int DescendantsSum
{
get
{
var sum = 0;
foreach(var child in Children)
{
sum += child.TreeSum;
//You can do this instead
//sum += child.Val;
//sum += child.DescendantsSum;
}
return sum;
}
}
/// <summary>
/// Sum of values in tree whose root is this node
/// </summary>
public int TreeSum { get { return Val + DescendantsSum; } }
}
或者使用LINQ:
public int DescendantsSum
{
get
{
return Children.Sum(child => child.TreeSum);
}
}
我不打算讨论自顶向下和自底向上的算法。你选择了自下而上,好吧,那么缺陷在哪里呢?
考虑下面的简单树:
child1
parent - grandparent
/
child2
你的算法将做:
parent.DescendantsSum += child1.TreeSum;
grandparent.DescendantsSum += parent.TreeSum;
parent.DescendantsSum += child2.TreeSum;
grandparent.DescendantsSum += parent.TreeSum;
可以看到,parent.TreeSum
被两次添加到grandparent.DescendantsSum
上,这导致了不正确的结果。
由于DescendantsSum
实际上是所有后代节点Val
的总和,因此修复算法的一种方法是处理所有节点并将节点Val
添加到每个节点的父节点。
static void SetSums(Node[] nodes)
{
foreach (var node in nodes)
node.DescendantsSum = 0;
foreach (var node in nodes)
for (var parent = node.Parent; parent != null; parent = parent.Parent)
parent.DescendantsSum += node.Val;
}
你需要一个递归函数
class NodeTest
{
public static void Run()
{
var root = new Node() { Val = 1 };
var a1 = new Node() { Val = 2 };
var a2 = new Node() { Val = 3 };
var a11 = new Node() { Val = 4 };
var a12 = new Node() { Val = 5 };
var a13 = new Node() { Val = 6 };
var a21 = new Node() { Val = 7 };
var a22 = new Node() { Val = 8 };
a1.Children.AddRange(new Node[] { a11, a12, a13 });
a2.Children.AddRange(new Node[] { a21, a22 });
root.Children.AddRange(new Node[] { a1, a2 });
Console.WriteLine(root.DescendantsSum);
Console.WriteLine(root.TreeSum);
Console.WriteLine();
Console.WriteLine(a1.DescendantsSum);
Console.WriteLine(a1.TreeSum);
}
}
class Node
{
public int Val { get; set; }
public List<Node> Children { get; set; }
/// <summary>
/// Sum of values in descendant nodes
/// </summary>
public int DescendantsSum
{
get
{
return TreeSum - Val;
}
}
/// <summary>
/// Sum of values in tree whose root is this node
/// </summary>
public int TreeSum
{
get
{
return GetTreeSum(this);
}
}
public Node()
{
Children = new List<Node>();
}
private int GetTreeSum(Node node)
{
int result = 0;
if (node.Children.Count > 0)
{
result += node.Val;
node.Children.ForEach(c => { result += GetTreeSum(c); });
}
else
result += node.Val;
return result;
}
}