Untitled
unknown
plain_text
a year ago
1.2 kB
3
Indexable
Never
#include <iostream> #include <vector> using namespace std; struct Node { int cost; vector<Node *> children; Node *parent; }; void helper(Node *root, int sum_cost, int &ans){ sum_cost += root->cost; if(root->children.size() == 0){ ans = min(ans, sum_cost); return; } for(int index = 0; index < root->children.size(); index++){ helper(root->children[index], sum_cost, ans); } } int getCheapestCost( Node *rootNode ) { // your code goes here if(!rootNode) return 0; int ans = INT_MAX; helper(rootNode, 0, ans); return ans; } int main() { Node* root = new Node; root->cost = 0; root->children.push_back(new Node); root->children.push_back(new Node); root->children.push_back(new Node); root->children[0]->cost = 5; root->children[1]->cost = 5; root->children[2]->cost = 6; cout << getCheapestCost(root) << endl; return 0; } /* Complexity: Time: O(n) // where, n is the total number of nodes. Extra Space: O(n) 1 2 3 3 2 3 5 */
Leave a Comment