bunnybare
BAN USERyea
void sortN( int * x, int N ) {
int i = 0;
int j = N-1;
int pivot = 0;
while( i <= j )
{
while ( x[i] < pivot && i < N ) i++;
while ( x[j] >= pivot && j >= 0) j--;
if ( i < j ) swap( x[i], x[j] );
}
}
void swap( int & x, int &y ){
int temp = x;
x = y;
y = temp;
}
Assumptions:
I'm printing the common ancestor.
II'm given a TreeNode structure that has a left and right pointer.
data is an int
a is 1000
b is 1
int common( TreeNode* root, int a, int b ){
if ( root == null ) return 0;
int leftCount = common(root->left, a, b);
int rightCount = common(root->right, a,b);
int mine;
// can't be both, right?
mine = ( root->data == a )? 1000: 0;
mine = ( root->data == b )? 1: 0;
// found already deeper in the tree
if ( leftCount == 1001 || rightCount == 1001) return 1001;
// nothing in my children, return my count
if ( leftCount == rightCount == 0 ) return mine;
// if we are here, the checks above arent true
// so check if we found something
if ( (leftCount + rightCount == 1001)
|| (mine + leftCount + rightCount == 1001) ){
// print
std::cout << "Here: " << root->data << std::endl;
// found
return 1001;
}
// left and right children doesnt have a AND b, so we're here
// possible they have either one though,
// mine isn't a or b so return children count
if ( mine == 0 && (leftCount != rightCount) )
return leftCount+rightCount ;
// both children had the same node data ( both a or both b)
else if( mine == 0 && leftCount == rightCount ) return leftCount;
// if I have same data as one of my children
// just return their count
else if ( mine == leftCount ) return leftCount ;
else if( mine == rightCount ) return rightCount ;
return mine;
}
Print left first, then mine, then right so order is preserved in printing.
void printRange( TreeNode *root, int min, int max ) {
if ( root == NULL ) return;
if ( root->data > min ) {
printRange( root->left, min, max );
}
if ( ( root->data > min ) && (root->data < max) ) {
std::cout << root->data << ",";
}
if (root->data < max) {
printRange( root->right, min, max);
}
}
1,3 and 2,5 overlap in the same interval.
- bunnybare October 19, 2014So, 1->5 is 4 and 8->9 is 1 for a total of 5.