1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | int LCA(node * root, int a, int b){ // find and return arr vector<int> arra,arrb; findnode(root,a,b,arra,arrb,false,false); for(int i = 0 ; i < min(arra.size(),arrb.size()) ; i++){ if(arra.at(arra.size()-i-1) != arrb.at(arrb.size()-1-i)){ return arra.at(arra.size()-i); } } return arra.size()>arrb.size()? arrb.at(0) : arra.at(0); } void findnode(node * curr, int a, int b, vector<int> & arra, vector<int> &arrb, bool founda, bool foundb){ if(curr==NULL){ return; } if(founda==false){ arra.push_back(curr->data); } if(foundb==false){ arrb.push_back(curr->data); } if(curr->data == a){ founda = true; } if(curr->data == b){ foundb = true; } findnode(curr->left,a,b,arra,arrb,founda,foundb); findnode(curr->right,a,b,arra,arrb,founda,foundb); if(founda!=true){ arra.pop_back(); } if(foundb!=true){ arrb.pop_back(); } | cs |