销售路径树问题 DFS 实施
Sales Path Tree Problem DFS implementation
有人可以向我解释一下我的代码中的错误是什么吗？我正在尝试解决这个问题作为练习，但我不断收到堆栈溢出错误。我一直在查看它，但似乎无法找到我的代码中溢出堆栈的位置。一些注意事项：
- 我在我的代码中实际上不理解我在测试用例中创建的子节点如何“知道”他们的父节点是谁——因此，我添加了那些将他们的父节点分配给根节点的行节点以防万一。我知道这可能看起来不太好，但我只是想弄清楚我的主要问题！
- 我最初在创建新的 SalesNode[=29 时将 parent 和 children 的值初始化为 null =] 对象，但是我遇到了 NullReferenceExceptions，所以我也将这部分更改为安全网。
问题：
The car manufacturer Honda holds their distribution system in the form of a tree (not necessarily binary). The root is the company
itself, and every node in the tree represents a car distributor that
receives cars from the parent node and ships them to its children
nodes. The leaf nodes are car dealerships that sell cars direct to
consumers. In addition, every node holds an integer that is the cost
of shipping a car to it.
Take for example the tree below:
0
/ | \
5 3 6
/ / \ / \
4 2 0 1 5
/ /
1 10
\
1
A path from Honda’s factory to a car dealership, which is a path from the root to a leaf in the > tree, is called a Sales Path. The cost of a Sales Path is the sum of the costs for every node
in the path. For example, in the tree above one Sales Path is
0→3→0→10, and its cost is 13 (0+3+0+10).
Honda wishes to find the minimal Sales Path cost in its distribution
tree. Given a node rootNode, write a function getCheapestCost that
calculates the minimal Sales Path cost in the tree.
Implement your function in the most efficient manner and analyze its
time and space complexities.
For example:
Given the rootNode of the tree in diagram above
Your function would return:
7 since it’s the minimal Sales Path cost (there are actually two Sales
Paths in the tree whose cost is 7: 0→6→1 and 0→3→2→1→1)
我的代码：
using System;
using System.Collections;
class SalesNode
{
public int cost;
public SalesNode[] children;
public SalesNode parent;
public SalesNode()
{
children = new SalesNode[0];
parent = new SalesNode();
}
}
class Solution
{
static void Main(string[] args)
{
SalesNode rootNode = new SalesNode();
rootNode.children = new SalesNode[3];
rootNode.cost = 0;
rootNode.children[0] = new SalesNode {cost = 5};
rootNode.children[1] = new SalesNode {cost = 3};
rootNode.children[2] = new SalesNode {cost = 6};
rootNode.children[0].parent = rootNode;
rootNode.children[1].parent = rootNode;
rootNode.children[2].parent = rootNode;
Console.WriteLine(getCheapestCost(rootNode));
}
public static int getCheapestCost(SalesNode rootNode) {
int minSalesPathCost = Int32.MaxValue;
int currentPathCost = 0;
// Create a stack to implement DFS
Stack salesNodeStack = new Stack();
SalesNode currentNode;
salesNodeStack.Push(rootNode);
while (salesNodeStack.Count > 0) { // Stack is not empty
currentNode = (SalesNode) salesNodeStack.Pop();
currentPathCost += currentNode.cost;
if (currentNode.children.Length == 0) { // Current node is a leaf
minSalesPathCost = Math.Min(minSalesPathCost, currentPathCost);
do { // Keep subtracting costs until back to parent node of next unexplored path
currentPathCost -= currentNode.cost;
currentNode = currentNode.parent;
} while (currentNode != rootNode && currentNode.children.Length == 1);
} else { // Current node has children
foreach (SalesNode child in currentNode.children) {
salesNodeStack.Push(child);
}
}
}
return minSalesPathCost;
}
}
非常感谢任何见解。谢谢大家！
堆栈溢出的原因是SalesNode构造函数中parent字段的初始化。您可以通过使用 new SalesNode() 调用其构造函数来创建 SalesNode 的新实例。构造函数依次创建 SalesNode 的新实例以初始化 parent 字段，从而调用自身。对构造函数的原始调用永远不会完成，因为它陷入了一个循环，试图创建一个无限长的 SalesNode 实例链，每个实例都有另一个 SalesNode 实例作为其 parent 属性，最终堆栈完全充满了对控制应该 return 到 if/when 的引用，其中一个对构造函数的调用曾经完成。奇怪的是，当我尝试你的代码时（在 Visual Studio 2019 中使用 .net core 3.1），堆栈溢出异常没有堆栈跟踪，所以我明白为什么这很难调试。
您应该问自己的第一个问题是 SalesNode 是否真的需要知道它的 parent 节点是什么。如果是，则不要在 child 节点的构造函数中实例化 parent 节点，而是更改构造函数的签名，以便您可以将 parent SalesNode 传递给它已经实例化了。这就解决了堆栈溢出异常。
public SalesNode(SalesNode parent)
{
this.children = new SalesNode[0];
this.parent = parent;
}
但是，我不相信 SalesNode 确实需要知道它的 parent 节点是什么。看起来 salesNodeStack 的目的可能是跟踪 getCheapestCost 方法在树中的位置，因此如果到达叶节点则去哪个节点，检查它是否最便宜, 然后需要导航到 parent 以评估另一条路径的成本。但这并不是该方法的实际实现方式。
你用的测试数据是这样的树
0
|
+---+---+
| | |
5 3 6
注释掉 SalesNode 的 parent 字段及其初始化，在调试器中单步执行代码，我看到在进入 while (salesNodeStack.Count > 0) 循环时，currentNode 设置为根节点。到此为止。
这个节点有 3 children，所以控制权转到 else 块，它将每个它的 3 children 推到 salesNodeStack 然后传递控制权回到 while (salesNodeStack.Count > 0) 循环的开始。这次，currentNode 被设置为最后一个 child 节点，它被推到 salesNodeStack 上，成本为 6，因为它没有任何 children ，minSalesPathCost 正确设置为 6 + 0，因为这是要评估的第一个叶节点，因此它是迄今为止看到的最便宜的节点。
内部循环的实现似乎与评论中描述的意图不符。
do
{ // Keep subtracting costs until back to parent node of next unexplored path
currentPathCost -= currentNode.cost;
//currentNode = currentNode.parent;
currentNode = (SalesNode)salesNodeStack.Pop();
} while (currentNode != rootNode && currentNode.children.Length == 1);
我注释掉了对 currentNode.parent 的引用，因为我已经从 SalesNode class 中删除了该字段以解决堆栈溢出异常，而是尝试弹出parent 节点离开 salesNodeStack，但这实际上不起作用，因为堆栈中的下一个项目不是节点的 parent，而是节点的前一个兄弟节点。并且因为前一个兄弟没有恰好 1 children（它有 none），这个循环退出。所以我们又回到了 while (salesNodeStack.Count > 0) 循环的开始。
现在根节点的第一个 child 被弹出堆栈（我们已经完全跳过了计算成本为 3 的节点）并且我们计算它的成本，它达到 5，这是正确的如果你忽略了我们忽略了成本为 3 的节点这一事实。
但是 currentNode = (SalesNode)salesNodeStack.Pop() 抛出一个 InvalidOperationException 因为 salesNodeStack 现在是空的，所以没有什么可以弹出的。
我认为您需要关注解决方案的两个方面（除了 SalesNode 构造函数总是尝试实例化另一个 SalesNode 这一事实）是...
foreach (SalesNode child in currentNode.children)
{
salesNodeStack.Push(child);
}
与其将一个节点的所有（立即）children 推入堆栈，也许您应该导航到一个 child 节点，将其推入堆栈，检查是否 child 节点有 children，如果有，导航到其中一个并将其推入堆栈，并重复直到到达叶节点？
} while (currentNode != rootNode && currentNode.children.Length == 1);
这个内部循环的退出条件实际上并没有检查我们是否回到了一个 parent 尚未访问的路径的节点（这就是 currentPathCost -= currentNode.cost 暗示它应该这样做）。这个条件究竟应该是什么取决于你如何在评估路径成本之前实现一直向下到叶节点的导航。您可能需要在 SalesNode class 中添加一个 property/field 以表明它是否已经被访问过。
您可能需要考虑的其他一些事项...
您的测试数据是一棵只有一级 child 节点的树。我认为这不足以正确测试您的代码。您问题中发布的树将是一个更好的测试用例 - 尝试在您的测试数据中实现它。
0
|
+-----+-------+
| | |
5 3 6
| | |
+ +-+-+ +-+-+
| | | | |
4 2 0 1 5
| |
+ +
| |
1 10
|
+
|
1
您可以将 salesNodeStack 的类型从 System.Collections.Stack 更改为 System.Collections.Generic.Stack<SalesNode>。它没有任何功能上的区别，但它是类型安全的；它保证堆栈中的所有内容都是 SalesNode 的一个实例，并且让您不必在从堆栈弹出后将每个对象强制转换为 SalesNode。
您还可以将 SalesNode 的 children 字段的类型从数组更改为 System.Collections.Generic.List<SalesNode>。与 Stack<T> class 一样，它是类型安全的，并且与数组不同，它可以在您向其中添加项目或从中删除项目时扩大和缩小。
有人可以向我解释一下我的代码中的错误是什么吗？我正在尝试解决这个问题作为练习，但我不断收到堆栈溢出错误。我一直在查看它，但似乎无法找到我的代码中溢出堆栈的位置。一些注意事项：
- 我在我的代码中实际上不理解我在测试用例中创建的子节点如何“知道”他们的父节点是谁——因此，我添加了那些将他们的父节点分配给根节点的行节点以防万一。我知道这可能看起来不太好，但我只是想弄清楚我的主要问题！
- 我最初在创建新的 SalesNode[=29 时将 parent 和 children 的值初始化为 null =] 对象，但是我遇到了 NullReferenceExceptions，所以我也将这部分更改为安全网。
问题：
The car manufacturer Honda holds their distribution system in the form of a tree (not necessarily binary). The root is the company itself, and every node in the tree represents a car distributor that receives cars from the parent node and ships them to its children nodes. The leaf nodes are car dealerships that sell cars direct to consumers. In addition, every node holds an integer that is the cost of shipping a car to it.
Take for example the tree below:
0 / | \ 5 3 6 / / \ / \ 4 2 0 1 5 / / 1 10 \ 1A path from Honda’s factory to a car dealership, which is a path from the root to a leaf in the > tree, is called a Sales Path. The cost of a Sales Path is the sum of the costs for every node in the path. For example, in the tree above one Sales Path is 0→3→0→10, and its cost is 13 (0+3+0+10).
Honda wishes to find the minimal Sales Path cost in its distribution tree. Given a node rootNode, write a function getCheapestCost that calculates the minimal Sales Path cost in the tree.
Implement your function in the most efficient manner and analyze its time and space complexities.
For example:
Given the rootNode of the tree in diagram above
Your function would return:
7 since it’s the minimal Sales Path cost (there are actually two Sales Paths in the tree whose cost is 7: 0→6→1 and 0→3→2→1→1)
我的代码：
using System;
using System.Collections;
class SalesNode
{
public int cost;
public SalesNode[] children;
public SalesNode parent;
public SalesNode()
{
children = new SalesNode[0];
parent = new SalesNode();
}
}
class Solution
{
static void Main(string[] args)
{
SalesNode rootNode = new SalesNode();
rootNode.children = new SalesNode[3];
rootNode.cost = 0;
rootNode.children[0] = new SalesNode {cost = 5};
rootNode.children[1] = new SalesNode {cost = 3};
rootNode.children[2] = new SalesNode {cost = 6};
rootNode.children[0].parent = rootNode;
rootNode.children[1].parent = rootNode;
rootNode.children[2].parent = rootNode;
Console.WriteLine(getCheapestCost(rootNode));
}
public static int getCheapestCost(SalesNode rootNode) {
int minSalesPathCost = Int32.MaxValue;
int currentPathCost = 0;
// Create a stack to implement DFS
Stack salesNodeStack = new Stack();
SalesNode currentNode;
salesNodeStack.Push(rootNode);
while (salesNodeStack.Count > 0) { // Stack is not empty
currentNode = (SalesNode) salesNodeStack.Pop();
currentPathCost += currentNode.cost;
if (currentNode.children.Length == 0) { // Current node is a leaf
minSalesPathCost = Math.Min(minSalesPathCost, currentPathCost);
do { // Keep subtracting costs until back to parent node of next unexplored path
currentPathCost -= currentNode.cost;
currentNode = currentNode.parent;
} while (currentNode != rootNode && currentNode.children.Length == 1);
} else { // Current node has children
foreach (SalesNode child in currentNode.children) {
salesNodeStack.Push(child);
}
}
}
return minSalesPathCost;
}
}
非常感谢任何见解。谢谢大家！
堆栈溢出的原因是SalesNode构造函数中parent字段的初始化。您可以通过使用 new SalesNode() 调用其构造函数来创建 SalesNode 的新实例。构造函数依次创建 SalesNode 的新实例以初始化 parent 字段，从而调用自身。对构造函数的原始调用永远不会完成，因为它陷入了一个循环，试图创建一个无限长的 SalesNode 实例链，每个实例都有另一个 SalesNode 实例作为其 parent 属性，最终堆栈完全充满了对控制应该 return 到 if/when 的引用，其中一个对构造函数的调用曾经完成。奇怪的是，当我尝试你的代码时（在 Visual Studio 2019 中使用 .net core 3.1），堆栈溢出异常没有堆栈跟踪，所以我明白为什么这很难调试。
您应该问自己的第一个问题是 SalesNode 是否真的需要知道它的 parent 节点是什么。如果是，则不要在 child 节点的构造函数中实例化 parent 节点，而是更改构造函数的签名，以便您可以将 parent SalesNode 传递给它已经实例化了。这就解决了堆栈溢出异常。
public SalesNode(SalesNode parent)
{
this.children = new SalesNode[0];
this.parent = parent;
}
但是，我不相信 SalesNode 确实需要知道它的 parent 节点是什么。看起来 salesNodeStack 的目的可能是跟踪 getCheapestCost 方法在树中的位置，因此如果到达叶节点则去哪个节点，检查它是否最便宜, 然后需要导航到 parent 以评估另一条路径的成本。但这并不是该方法的实际实现方式。
你用的测试数据是这样的树
0
|
+---+---+
| | |
5 3 6
注释掉 SalesNode 的 parent 字段及其初始化，在调试器中单步执行代码，我看到在进入 while (salesNodeStack.Count > 0) 循环时，currentNode 设置为根节点。到此为止。
这个节点有 3 children，所以控制权转到 else 块，它将每个它的 3 children 推到 salesNodeStack 然后传递控制权回到 while (salesNodeStack.Count > 0) 循环的开始。这次，currentNode 被设置为最后一个 child 节点，它被推到 salesNodeStack 上，成本为 6，因为它没有任何 children ，minSalesPathCost 正确设置为 6 + 0，因为这是要评估的第一个叶节点，因此它是迄今为止看到的最便宜的节点。
内部循环的实现似乎与评论中描述的意图不符。
do
{ // Keep subtracting costs until back to parent node of next unexplored path
currentPathCost -= currentNode.cost;
//currentNode = currentNode.parent;
currentNode = (SalesNode)salesNodeStack.Pop();
} while (currentNode != rootNode && currentNode.children.Length == 1);
我注释掉了对 currentNode.parent 的引用，因为我已经从 SalesNode class 中删除了该字段以解决堆栈溢出异常，而是尝试弹出parent 节点离开 salesNodeStack，但这实际上不起作用，因为堆栈中的下一个项目不是节点的 parent，而是节点的前一个兄弟节点。并且因为前一个兄弟没有恰好 1 children（它有 none），这个循环退出。所以我们又回到了 while (salesNodeStack.Count > 0) 循环的开始。
现在根节点的第一个 child 被弹出堆栈（我们已经完全跳过了计算成本为 3 的节点）并且我们计算它的成本，它达到 5，这是正确的如果你忽略了我们忽略了成本为 3 的节点这一事实。
但是 currentNode = (SalesNode)salesNodeStack.Pop() 抛出一个 InvalidOperationException 因为 salesNodeStack 现在是空的，所以没有什么可以弹出的。
我认为您需要关注解决方案的两个方面（除了 SalesNode 构造函数总是尝试实例化另一个 SalesNode 这一事实）是...
foreach (SalesNode child in currentNode.children)
{
salesNodeStack.Push(child);
}
与其将一个节点的所有（立即）children 推入堆栈，也许您应该导航到一个 child 节点，将其推入堆栈，检查是否 child 节点有 children，如果有，导航到其中一个并将其推入堆栈，并重复直到到达叶节点？
} while (currentNode != rootNode && currentNode.children.Length == 1);
这个内部循环的退出条件实际上并没有检查我们是否回到了一个 parent 尚未访问的路径的节点（这就是 currentPathCost -= currentNode.cost 暗示它应该这样做）。这个条件究竟应该是什么取决于你如何在评估路径成本之前实现一直向下到叶节点的导航。您可能需要在 SalesNode class 中添加一个 property/field 以表明它是否已经被访问过。
您可能需要考虑的其他一些事项...
您的测试数据是一棵只有一级 child 节点的树。我认为这不足以正确测试您的代码。您问题中发布的树将是一个更好的测试用例 - 尝试在您的测试数据中实现它。
0
|
+-----+-------+
| | |
5 3 6
| | |
+ +-+-+ +-+-+
| | | | |
4 2 0 1 5
| |
+ +
| |
1 10
|
+
|
1
您可以将 salesNodeStack 的类型从 System.Collections.Stack 更改为 System.Collections.Generic.Stack<SalesNode>。它没有任何功能上的区别，但它是类型安全的；它保证堆栈中的所有内容都是 SalesNode 的一个实例，并且让您不必在从堆栈弹出后将每个对象强制转换为 SalesNode。
您还可以将 SalesNode 的 children 字段的类型从数组更改为 System.Collections.Generic.List<SalesNode>。与 Stack<T> class 一样，它是类型安全的，并且与数组不同，它可以在您向其中添加项目或从中删除项目时扩大和缩小。