노드 포인터보다는 데이터와 가장 가까운 가장 가까운 조상 함수

Question

BST가 아닌 이진 트리에서 가장 가까운 조상을 찾기위한 프로그램을 작성 중입니다. 나는 다음과 같은 일을하려고 (통과에만 데이터 값과 포인터에 관심없는 조상의 데이터 값, 찾을 수)

int closestanc(node * root, int n1, int n2) 
{ 
    int l, r; 
    if(root == NULL) 
     return -1; 
    if(root->right->data == n1 || root->right->data == n2 || root->left->data == n1 ||  root->left->data == n2) 
     return root->data; 
    else 
    { 
     l = closestanc(root->left, n1, n2); 
     r = closestanc(root->right, n1, n2); 
     if(l!= -1 && r!= -1) 
      return root->data; 
     else 
      return (l != -1 ? l : r); 
    } 
} 

Answer 1

을하고

mynode *closestAncestor(mynode* root, mynode* p, mynode* q) 
{ 
    mynode *l, *r, *tmp; 

    if(root == NULL) 
    { 
     return(NULL); 
    } 

if(root->left==p || root->right==p || root->left==q || root->right==q) 

    { 
    return(root); 
    } 
    else 
    { 
     l = closestAncestor(root->left, p, q); 
     r = closestAncestor(root->right, p, q); 

     if(l!=NULL && r!=NULL) 
     { 
     return(root); 
     } 
     else 
     { 
     tmp = (l!=NULL) ? l : r; 
     return(tmp); 
     } 
    } 
} 

: 나는 샘플 작업 코드 발견

NULL을 확인해야합니다. 변경 :

if(root->right->data == n1 || root->right->data == n2 || 
    root->left->data == n1 || root->left->data == n2) 

당신이로 교체 할 수 있습니다 생각하지만

if ((root->right != NULL && (root->right->data == n1 || root->right->data == n2)) 
|| (root->left != NULL && (root->left->data == n1 || root->left->data == n2))) 

에 대한 간단한 :

if (root->data == n1 || root->data == n2) 

함수가 출력이 (그것이 작동하는 방법이 변경됩니다 있지만 무엇을 변경하지 않고 약간).

추가 참고 :

기능은 정확히 너무 신뢰할 수 없습니다. 둘 다 나무에 없으면 여전히 조상을 돌려 줄 것입니다. 이를 위의 확인을 위해 root->data; 대신 -2 (또는 다른 사용하지 않은 값)을 반환하는 것이 좋습니다. 그러면 두 가지가 모두 발견되지 않을 때 확인할 수 있습니다. 그래서

: 다음

if (root->data == n1 || root->data == n2) 
    return -2; 

: 함수가 -1 반환하면

• , 당신은 요소 중 어느 것도 발견되었다 알고있다.
• -2을 반환하면 그 중 하나만 찾았습니다.
• 다른 것이 있으면 가장 가까운 조상입니다.