0

我正在尝试实现一个函数来计算二叉树的路径长度，但我无法得到正确的答案。你能检查我做错了什么吗？下面是我的代码：

public int pathLength() {
    int sum = 0;
    int c = 1;
    pathLength(root, sum);
    return sum;
}

public int pathLength(Node n, int sum) {
    if(n.isRoot())
        sum+= 0;
    if(n.left == null && n.right == null)
        return;
    c++;
    if(n.left != null)
        sum += c;
    if (n.right != null)
        sum+=c;
    pathLength(n.left, sum);
    pathLength(n.right, sum); 

}
4

3 回答 3

1

这段代码有很多问题。它甚至不会编译，因为 a）在第二个函数中 c 从未声明（它在第一个函数中是本地的）和 b）第二个函数从不返回值。

但最大的问题是你声明第二个函数的方式。“sum”按值传递。这基本上意味着每次调用函数时都会创建一个新的“sum”副本，并在函数结束时被丢弃。

你想要做的是通过引用传递。这样做时，实际的 sum 变量，而不是副本，被传递给函数。因此，您的代码可能如下所示：

public void pathLength(Node n, int& sum) {
    //if(n.isRoot())     <- not sure what this is for
    //    sum+= 0;

    sum += 1;   // Increment for this node

    //if(n.left == null && n.right == null)
    //    return;      // This conditional is not needed with next 2 if statements

    //c++;    <- Don't know what c is for

    // Recursively call for child nodes
    if(n.left != null)
        pathLength(n.left, sum);
    if (n.right != null)
        pathLength(n.right, sum); 
}

请注意，这会计算树中的所有节点。我想这就是你想要的。如果你想找到最深的节点，那就不同了。

于 2012-11-17T06:02:37.833 回答
0

是不是因为你把c的初始值设置为1而不是0？root 的子节点应该在第 2 层，深度为 1。

于 2018-05-02T11:29:34.737 回答
0

这是一个简单的方法时间：O（n）而空间将是O（h），其中h是二叉树的高度：

int sum(BinaryTree *node, int count){
    if(node == nullptr){
        return 0;
    }
    

    return count + sum(node->left, count+1)+sum(node->right, count+1);
}

int nodeDepths(BinaryTree *root) {
    int count=0;
    int ans=0;
    ans =sum(root, count);
  return ans;

    }
于 2022-02-16T13:19:11.227 回答