prity
BAN USER1)Simplest way is to do BFS and check every node
2)if current node is leaf node then we check for two conditions
2.1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
2.2)If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
int samelevelcheck(node *root)
{
// Base Case
if (root == NULL)
return 0;
queue<node *> q;
// Enqueue Root
q.push(root);
while (1)
{
// nodeCount (queue size) indicates number of nodes at current level.
int nodeCount = q.size();
if (nodeCount == 0)
return 1;
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
node *newnode = q.front();
q.pop();
if (newnode->left != NULL)
q.push(newnode->left);
if (newnode->right != NULL)
q.push(newnode->right);
//if current node is leaf node then we check for two conditions
if((newnode->left== NULL && newnode->right== NULL))
{
//1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
if((nodeCount==1 && q.size()>0))
return 0;
//If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
else
{
nodeCount = q.size();
while(nodeCount>0)
{
node *temp = q.front();
q.pop();
if(temp->left||temp->right)
return 0;
nodeCount--;
}
}
}
nodeCount--;
}
}
return 1;
}
1)The main idea of this approach is to do a BFS and check each node.
2)If current node is leaf node then we check for two conditions
2.1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
2.2)If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
// Iterative method to check whether all leaf are at same level or not
int samelevelcheck(node *root)
{
// Base Case
if (root == NULL)
return 0;
// Create an empty queue for level order tarversal
queue<node *> q;
q.push(root);
while (1)
{
// nodeCount (queue size) indicates number of nodes at current level.
int nodeCount = q.size();
if (nodeCount == 0)
return 1;
// Dequeue all nodes of current level and Enqueue all
// nodes of next level
while (nodeCount > 0)
{
node *newnode = q.front();
q.pop();
if (newnode->left != NULL)
q.push(newnode->left);
if (newnode->right != NULL)
q.push(newnode->right);
/*if current node is leaf node then we check for two conditions
if((newnode->left== NULL && newnode->right== NULL))
{
//1)If it is extreme right leaf node of that level, then there shouldn't be any node following.(i.e queue should be empty)
if((nodeCount==1 && q.size()>0))
return 0;
//If it is any other leaf node then we check that any of the following node in that level must also be a leaf node
else
{
nodeCount = q.size();
while(nodeCount>0)
{
node *temp = q.front();
q.pop();
if(temp->left||temp->right)
return 0;
nodeCount--;
}
}
}
nodeCount--;
}
}
return 1;
}
void ZigZacTraversal(struct btree *root)
{
struct btree *Stack1[20],*Stack2[20],*temp;
int top1=-1,top2=-1,LeftToRight=1;
int flag1=0,flag=0;
Stack1[++top1]=root;
while(top1>=0 || top2>=0)
{
if(LeftToRight)
{
while(top1>=0)
{
temp=Stack1[top1--];
if(flag==0){printf("%d ",temp->data); flag=1;}
if(temp->left)
Stack2[++top2]=temp->left;
if(temp->right)
Stack2[++top2]=temp->right;
}
printf("|");
flag=0;
}
else
{
while(top2>=0)
{
temp=Stack2[top2--];
if(flag1==0){printf("%d ",temp->data); flag1=1;}
if(temp->right)
Stack1[++top1]=temp->right;
if(temp->left)
Stack1[++top1]=temp->left;
}
printf("|");
flag1=0;
}
LeftToRight=1-LeftToRight;
}
}
void ZigZacTraversal(struct btree *root)
{
struct btree *Stack1[20],*Stack2[20],*temp;
int top1=-1,top2=-1,LeftToRight=1;
int flag1=0,flag=0;
Stack1[++top1]=root;
while(top1>=0 || top2>=0)
{
if(LeftToRight)
{
while(top1>=0)
{
temp=Stack1[top1--];
if(flag==0){printf("%d ",temp->data); flag=1;}
if(temp->right)
Stack2[++top2]=temp->right;
if(temp->left)
Stack2[++top2]=temp->left;
}
printf("|");
flag=0;
}
else
{
while(top2>=0)
{
temp=Stack2[top2--];
if(flag1==0){printf("%d ",temp->data); flag1=1;}
if(temp->left)
Stack1[++top1]=temp->left;
if(temp->right)
Stack1[++top1]=temp->right;
}
printf("|");
flag1=0;
}
LeftToRight=1-LeftToRight;
}
}
#include<stdio.h>
#include<conio.h>
char m[4][4] =
{ { 'x', 'x','x','x'},
{ 'x', 'x','o','x'},
{ 'x', 'x','x','o'},
{ 'x', 'x','x','x'}};
int row=4,col=4;
int noofwayspsbl(int p,int q)
{
if (p>row-1 || q>col-1 || m[p][q]=='o') return 0;
if (p==row-1 && q==col-1 && m[p][q]=='x') return 1;
return (noofwayspsbl(p+1,q)) + (noofwayspsbl(p,q+1));
}
int main()
{
printf("\n Possible no of paths is = %d",noofwayspsbl(0,0));
getch();
return 0;
}
#include<stdio.h>
#include<conio.h>
char m[4][4] =
{ { 'x', 'x','x','x'},
{ 'x', 'x','o','x'},
{ 'x', 'x','x','o'},
{ 'x', 'x','x','x'}};
int row=4,col=4;
int noofwayspsbl(int p,int q)
{
if (p>row-1 || q>col-1 || m[p][q]=='o') return 0;
if (p==row-1 && q==col-1 && m[p][q]=='x') return 1;
return (noofwayspsbl(p+1,q)) + (noofwayspsbl(p,q+1));
}
int main()
{
printf("\n Possible no of paths is = %d",noofwayspsbl(0,0));
getch();
return 0;
}
1)Find the minimum of all list's last index
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
which is 20 from List 2, take it as lower range.
2)Binary search in List 1 and List 3, and find its immediate greater value, which is 24 in List 1, and 22 in List 3.
3)Take the maximum of these two values as upper range(Which is 24).
4)Hence [20-24] is the required range.
Kindly correct me, if i am wrong.
Push the first element of array in a stack.
take rest of the elements one by one and follow following steps in loop.
a) Take second element of array as CURRENT element(i.e array[1])
b)Compare it with top of the stack.
c) If CURRENT element is greater
-Keep poping from the stack while the popped element is smaller than CURRENT. and CURRENT element is the next greater element for all such popped elements.
d)else just push the CURRENT element in the stack.
At the end of the loop, pop all the elements left in stack and print -1 as next element for them.
I think you didn't read the question properly. It is asked to print only meaningful anagrams which exists in dictionary , not all possible permutations.
- prity July 14, 2013