我的线性算法的缺陷在哪里

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; } }
}

/// <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;
}

当你在处理树时，有时从上到下更容易，而不是像你那样从上到下。

我想这应该能满足你的需要:

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;
        }
    }