AA
BAN USERI wrote exactly the same with slight modification.
private static void InitNext(TreeNode root)
{
if(root == null) return;
var mainQueue = new Queue<TreeNode>();
var childQueue = new Queue<TreeNode>();
TreeNode first = null;
mainQueue.Enqueue(root);
while (mainQueue.Count > 0)
{
var temp = mainQueue.Dequeue();
if (temp.Left != null)
childQueue.Enqueue(temp.Left);
if (temp.Right != null)
childQueue.Enqueue(temp.Right);
if (mainQueue.Count == 0)
{
temp= childQueue.Dequeue();
mainQueue.Enqueue(temp);
while (childQueue.Count > 0)
{
TreeNode second = childQueue.Enqueue();
temp.next = second;
temp = second;
mainQueue.Enqueue(second);
}
}
}
}
Here is C++ solution for this without using extra space and is O(log n ) in complexity..
#include<iostream>
#include <math.h>
using namespace std;
int getSum(int a[],int start,int size){
int sum =0;
for(int i=start;i<start+size;++i)
sum+=a[i];
return sum;
}
int findHeaviest(int a[],int start,int n){
if(start<0) return -1;
if(n==1) return start;
if(n==2){
if(a[start]>a[start+1]) return start;
return start+1;
}
int size;
if(n%3==0) size =n/3;
else size=n/3+1;
int LSum=getSum(a,start,size);
int RSum=getSum(a,start+size,size);
if(LSum==RSum) return findHeaviest(a,start+2*size,n-2*size);
if(LSum>RSum) return findHeaviest(a,start,size);
return findHeaviest(a,start+size,size);
}
int main(){
cout<<"Find Heaviest Element"<<endl;
int a[]={1,1,1,1,1,1,1,2,1};
int b[]={1,1,1,1,1,1,1,2,1,1,1,1,1};
int c[]={1,1,1,2,1,1,1,1};
cout<<"Heaviest index"<<findHeaviest(a,0,9)+1<<endl;
cout<<"Heaviest index"<<findHeaviest(b,0,13)+1<<endl;
cout<<"Heaviest index"<<findHeaviest(c,0,8)+1<<endl;
return 0;
}
Wonderful approach, few corrections and this work like a charm.
correctBST(root)
{
static Node* temp1,*temp2,*prev;
static int found;
if(found) return;
if(root)
{
correctBST(root->left);
if(!temp1 && prev && root->data<prev->data)
temp1=prev;
else if(!temp2 && prev && root->data<prev->data)
temp2=root;
if(temp1 && temp2 && !found)
{
swap(&(temp1->data),&(temp2->data));
found=1;
return;
}
prev=root;
correctBST(root->right);
}
}
This simple code will work... some error checking will be needed but simple tree traversal is sufficient. but I think you can assume in beginning that N liters of water will fill in buckets with C capacity each.
void fillBuckets(BinaryTree * root,double C,double N){
if(!root) return;
double diff=C-root->val; // root->val is 0 initially for each bucket. some modification is needed is it can have other value
if(diff>=N){ //this bucket can take all water
root->val+=N;
N=0;
}else{ //fill bucket completely and spill remaining water. trick is we don't need to take care of any bucket getting overflow. simply spill water to lower levels. If bucket is filled completely by left parent, right will spill all water.
root->val+=diff;
N-=diff;
}
if(N>0){
fillBuckets(root->left,C,N/2);
fillBuckets(root->right,C,N/2);
}
}
For fillBuckets(root,5,40), this gives
5
5 5
5 5 5
.625 4.375 4.375 .625
please let me know if any thing is wrong.
Right way to do this !!!
- AA August 09, 2012