north_remembers
BAN USERI have used two integers, child_num and par_num to keep a track of parents and children.
when parents ==0, which means only children are present in the queue, we print.
public static void printLevel(Node root)
{
if(root==null)
return;
Queue q=new Queue();
q.enqueue(root);
q.par_num++;
while(q.size()>0)
{
Node temp=q.dequeue();
if(temp.left!=null)
q.enqueue(temp.left);
if(temp.right!=null)
q.enqueue(temp.left);
if(q.par_num==0)
q.printQueue();
q.par_num=q.child_num;
q.child_num=0;
}
}
class Queue
{
LinkedList<Node> list;
int child_num, par_num;
Queue()
{
list=new LinkedList<Node>();
child_num=0;
par_num=0;
}
public void enqueue(Node item)
{
child_num++;
list.addLast(item);
}
public Node dequeue()
{
par_num--;
if(list.size()==0)
return null;
else
return list.removeFirst();
}
public int size()
{
return list.size();
}
public void printQueue()
{
System.out.println();
for(int i=0;i<list.size();i++)
{
Node temp=list.get(i);
System.out.print(temp.value);
}
}
}
class Node
{
Node left;
Node right;
int value;
Node(Node left, Node right, int value)
{
this.left=left;
this.right=right;
this.value=value;
}
}
@kkr.ashish
How do you decide by what number to divide ? Like you used %4. For x it seems fine, as you start with x=4, and we are trying to get x relative to it. But for y also you have %4. Could you elaborate a bit...I guess I'm missing why you take (i-1)%4...
Because after reading your algo description I figured that in x you should take min(x) and max(x). Similarly for y you should get min(y) and max(y). Multiply difference between min-max x and min-max y
Thanks
This algorithm only finds if two nodes have a LCA, it doesn't return the node which is LCA
- north_remembers February 12, 2013Hi
I have the same solution as people are suggesting above. But as I had maximum sum sub sequence problem in my homework I would like to write down the logic. So the first point to note is that you can go only from P(i) to P(i+1). So i think taking a circular queue or a list would be wrong. Now you have two arrays, create a third array say arr
where arr[i]=P[i]-D[i];
And now follow this
For every element, find the OPT(i)=max{arr(i),arr(i)+OPT(i-1)}
And base case is OPT(i<0)=0 .
We fill the array from left to right, and the max value in the array would mark the beginning of the journey and where the OPT goes 0, that would mark the end. So the run time is 2n.
@Greatnose-But i don't get how the complexity comes out to be O(0) ? I mean in the worst case you end up travelling the whole array right ? this implies that complexity is O(n)
- north_remembers January 22, 2013
You must decide if you want to go for recursive function or iterative one. People tell me recursive is pretty but it uses stack memory and hence may bot be desirable some times. Here is my take
- north_remembers April 22, 2015