Mr.Giraffe
BAN USERI think we can just maintain a current node and compare the number of its left child and k, then move the current node. Here is my implementation and test cases.
#include <iostream>
using namespace std;
struct TreeNode{
int num, no;//the amount of nodes and the id
TreeNode *left, *right;
TreeNode(int _num, int _no):num(_num), no(_no), left(NULL), right(NULL){}
};
TreeNode* solve(TreeNode *root, int k){
if(root == NULL || root->num<k || k<=0) return NULL;
TreeNode *cur = root;
while(k > 0){
int lnum = cur->left?cur->left->num:0;
int rnum = cur->num-lnum-1;
if(k == lnum+1) return cur;
else if(k<=lnum){
cur = cur->left;
}else{
cur = cur->right;
k -= lnum+1;
}
}
return NULL;
}
int main(){
TreeNode *t1 = new TreeNode(10, 1);
TreeNode *t2 = new TreeNode(4, 2);
TreeNode *t3 = new TreeNode(5, 3);
TreeNode *t4 = new TreeNode(3, 4);
TreeNode *t5 = new TreeNode(2, 5);
TreeNode *t6 = new TreeNode(2, 6);
TreeNode *t7 = new TreeNode(1, 7);
TreeNode *t8 = new TreeNode(1, 8);
TreeNode *t9 = new TreeNode(1, 9);
TreeNode *t10 = new TreeNode(1, 10);
t1->left = t2;
t1->right = t3;
t2->left = t4;
t3->left = t5;
t3->right = t6;
t4->left = t7;
t4->right = t8;
t5->left = t9;
t6->right = t10;
cout<<solve(t1, 8)->no<<endl; //3
cout<<solve(t1, 5)->no<<endl; //1
cout<<solve(t1, 3)->no<<endl; //8
cout<<solve(t2, 3)->no<<endl; //8
cout<<solve(t3, 1)->no<<endl; //9
}
/*
10
/ \
4 5
/\ /\
3 0 2 2
/\ /\ /\
1 1 1 00 1
*/
In my oppnion, using a vector to hold the sorted elements may be a good solution. When the amount of elements is too big to put in a vector, I think this will be another quetion. Here is my implementation. I am new to careercup and hope to discuss with all of you. Thanks so much.
#include <cstdio>
#include <stack>
#include <vector>
#include <iostream>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int>::iterator vit;
vector<int> sorted_ele;
vit binary_search(vit begin, vit end, int ele){
int len = end - begin;
while(len>0){
int half = len>>1;
vit mid = begin+half;
if(*mid<ele){
begin = mid+1;
len -= half+1;
}else{
len = half;
}
}
return begin;
}
void insert(int ele, int len){
int pos = binary_search(sorted_ele.begin(), sorted_ele.end()-1, ele)-sorted_ele.begin();
for(int i=len;i>pos;--i){
sorted_ele[i] = sorted_ele[i-1];
}
sorted_ele[pos] = ele;
}
void push(stack<int> &s, int ele){
s.push(ele);
sorted_ele.resize(sorted_ele.size()+1);
insert(ele, sorted_ele.size()-1);
}
void pop(stack<int> &s){
if(s.empty()) return;
int x = s.top();
s.pop();
vit pos = binary_search(sorted_ele.begin(), sorted_ele.end(), x);
sorted_ele.erase(pos);
}
/*state:
0:success;
1:index<=0;
2:index exceed the amount of elements
*/
pii get(int i){
if(i<=0) return pii(1, -1);
else if(i>sorted_ele.size()) return pii(2, -1);
int len = sorted_ele.size();
return pii(0, sorted_ele[len-i]);
}
int main(){
stack<int> s;
for(int i=0;i<10;++i) push(s, i);
pii p = get(5);
printf("state: %d\tres: %d\n", p.first, p.second);
for(int i=0;i<5;++i) pop(s);
p = get(10);
printf("state: %d\tres: %d\n", p.first, p.second);
p = get(3);
printf("state: %d\tres: %d\n", p.first, p.second);
p = get(0);
printf("state: %d\tres: %d\n", p.first, p.second);
}
@wws 's idea is intreasting, I just not sure how to merge two nodes. Disjoint set may be a way, we can merge the neighbors of two nodes to their fathors, but other nodes may also point to two nodes who share their father, and I can fingure out an efficient way to merge this condition.
The nearest distance between two nodes cross my mind. If we define a directed graph like this: if x1<x2, then the distance d[x2][x1] = -1, if x1 == x2, d[x1][x2] = d[x2][x1] == 0, y is the same. I use floyd-warshall to get the distance between any two nodes and if there are a circle, the distance of d[i][i] will definite be negative.
I use test cases from @Adi, here is my implementation. Any comment/correction is welcome!
- Mr.Giraffe November 11, 2014