代码之家  ›  专栏  ›  技术社区  ›  J.D.

二叉树的根到节点的距离

  •  0
  • J.D.  · 技术社区  · 8 年前

    我必须找到二叉树的一个节点到其根的距离。

    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。有人能帮我吗? 谢谢。

    2 回复  |  直到 8 年前
        1
  •  1
  •   dbush    8 年前

    您正在使用逻辑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;
        }
    }
    
        2
  •  0
  •   saket garg    5 年前
    int findDistance(Node *root,int key)
    {
        if(root==NULL)
            return 1e9;
        if(root->data==key)
            return 0;
        return 1+min(findDistance(root->left,key),findDistance(root->right,key));
    }