哪里是我的线性算法

Question

缺陷鉴于像

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。我想过我的算法，我看不出它有什么缺陷。任何提示？

Answer 1

我不打算讨论自上而下VS自下而上的算法。你已经选择了自下而上的，很好，那么缺陷在哪里？

考虑以下简单的树：

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

Answer 2

当您使用树木时，从顶部到顶部而不是像其他方式一样，有时候会更容易。

我想这应该为你的工作需要：

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

Answer 3

你需要一个递归函数。
这工作得很好：

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