c - 二叉树的根到节点的距离

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

但它不起作用。事实上，我主要是这样做的:

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

您正在使用逻辑或运算符||来组合搜索左树和右树的结果。运算符的结果始终为 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;
    }
}