Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created November 15, 2017 07:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/68928470d1ee2e77e678c1a9d9692b15 to your computer and use it in GitHub Desktop.
Save jianminchen/68928470d1ee2e77e678c1a9d9692b15 to your computer and use it in GitHub Desktop.
Minimum path from root node to leaf node - use recursive function, I wrote with a bug in the writing and the peer told me to fix it. I added line 27 to line 32.
using System;
class Solution
{
public class Node
{
public int cost;
public Node[] children;
public Node(int value)
{
cost = value;
}
}
public static int getCheapestCost(Node rootNode) // node 0 ,
{
// base case
if(rootNode == null) // false
{
return 0;
}
var costRoot = rootNode.cost; // 0
int minimalPathCost = Int32.MaxValue;
var hasNoChildren = rootNode.children == null || rootNode.children.Length == 0;
if(hasNoChildren)
{
return costRoot;
}
foreach(var item in rootNode.children) // node 5, 3, 6, node 3
{
var current = getCheapestCost(item); // 9, 13, 7
var cost = costRoot + current; // 0 + 9 = 9, 13, 7
minimalPathCost = cost < minimalPathCost ? cost : minimalPathCost; // 9, 9, 7 < 9
}
return minimalPathCost; // 7
}
static void Main(string[] args)
{
Console.WriteLine("testing is here");
var root0 = new Node(0);
var root5 = new Node(5);
var root3 = new Node(3);
var root6 = new Node(6);
root0.children = new Node[]{root5, root3, root6};
var root4 = new Node(4);
root5.children = new Node[]{root4}; // path cost 9
var root1 = new Node(1);
root6.children = new Node[]{root1}; // path cost 7
var root10 = new Node(10);
root3.children = new Node[]{root10}; // path cost 13
Console.WriteLine("testing is here");
Console.WriteLine("path cost is "+ getCheapestCost(root0));
}
}
// root 0 -> Math.Min(node 5's find mininum, node 3's find minimum, node 6's minimum)
// 7 - path cost
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment