ルートからバイナリツリーのノードまでの距離

Question

バイナリツリーのノードのルートからの距離を求めなければなりません。 私の解決策は次のとおりです。

int distanceUtil(struct node* root, int x, int dist) { 
    if (root == NULL) { 
     return -1; 
    } 
    else { 
     if (root->data == x) { 
      return dist; 
     } 
     return distanceUtil(root->left, x, dist + 1) || distanceUtil(root->right, x, dist + 1); 
    } 
} 

int distance(struct node* root, int x) { 
    return distanceUtil(root, x, 0); 
} 

が、メインに私が行うとき、それはwork.In事実をしていません。

struct node* root = newNode(12); 
root->left = newNode(8); 
root->right = newNode(18); 
root->left->left = newNode(2); 
root->left->right = newNode(9); 
root->right->left = newNode(15); 
root->right->right = newNode(22); 
root->right->right->right = newNode(33); 
printf("il cammino : %d", distance(root,33)); 
getchar(); 
return 0; 

それは1を返しますが、誰かが私を助けることができるそれが3を返す必要がありますか？ ありがとうございます。

Answer 1

論理OR演算子||を使用して、左ツリーと右ツリーの検索結果を結合しています。演算子の結果は常に0または1なので、それ以外の結果は得られません。

あなたが本当に望むのは、各サブツリー検索の2つの値のうち大きい方を返すことです。だから、それぞれの側面を検索した結果を保存して、どれが大きいかを確認してそれを返します。

int distanceUtil(struct node* root, int x, int dist) { 
    if (root == NULL) { 
     return -1; 
    } 
    if (root->data == x) { 
     return dist; 
    } 

    int left = distanceUtil(root->left, x, dist + 1); 
    int right = distanceUtil(root->right, x, dist + 1); 
    if (left > right) { 
     return left; 
    } else { 
     return right; 
    } 
}