ksh
BAN USERWhat about this?
I am building up the nodes from top-bottom and assigning water to it.
I can know the 2 children of a node based on the level of a node, since at each level there are (level+1) nodes.
struct nodeInfo
{
int level;
int water;
}
int fillWater(int L, int C, int i /*0 based*/)
{
struct nodes[2*i] = {0};
nodes[0].level = 0;
nodes[0].water = L;
int index = 0;
while(index <= i)
{
int level = nodes[index].level;
int child1Index = index + level + 1;
int child2Index = index + level + 2;
nodes[child1Index].level = level + 1;
nodes[child2Index].level = level + 1;
if(nodeInfo[index].water > C)
{
nodes[child1Index].water += (nodes[index].water - C)/2;
nodes[child2Index].water += (nodes[index].water - C)/2;
}
index++;
}
return nodeInfo[i].water;
}
Since it is not a binary tree, this solution is wrong. We need to clone all the neighbors.
- ksh October 12, 2011But question also does not mention that it is a acyclic graph (or tree), so that is more difficult.