从根到二叉树节点的距离

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，因此除此之外，您不会得到任何结果。

你真正想要的是返回每个子树搜索的两个值中较大的一个。因此存储搜索每一边的结果，然后检查哪一个较大并返回。

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; 
    } 
}