카테고리 없음

tree recursion and returns

fw93 2018. 3. 25. 21:32
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