二叉树的直径

-1

“树的直径（有时称为宽度）是树中任意两个节点之间最长路径上的节点数”。二叉树的直径

下面的C++函数是否适用于所有情况下查找二叉树的直径？称为s=0，和该二进制树

int helper(node *root,int &s){ 

    int l = 0, r = 0; 

    if(root == NULL){ 
    return 0; 
    } 
    l= helper(root->left,s); //height of left subtree. 
    r= helper(root->right,s); //height of right subtree. 

    int mx_single=max(l,r)+1; 
    int mx_top=max(mx_single,l+r+1); 
    s=max(s,mx_top); 
    return mx_single; 
}

的root =根返回到主后，ans将s。

来源

2015-10-05 sb15

在很多情况下，我看起来错了，但是如果你的变量名称更具描述性，这将会有所帮助。该函数需要返回指定树的直径，但递归实现也需要使用每个子树的高度。

以你的直径定义为包括在计数叶节点，它可以递归改写像这样：

如果树包括单个节点的，那么它的直径是1（该整棵树是从一个叶节点到它自己的单节点路径）。
如果子树的根节点只有一个孩子，那么它的直径就是以该孩子为根的子树的直径。这是因为所有叶节点都在子树中，因此从叶到叶的所有非循环路径都局限于子树。
否则，直径在左子树的直径，右子树的直径以及两个子树的高度之和（在节点中测量）中是最大的。这考虑了最长的叶到叶路径包含在左侧子树中，包含在右侧子树中或通过根的可能性。在最后一种情况下，您不需要确定实际路径;子树高度告诉你它有多久（根节点+ 1节点）。

接收的子树的高度来处理第三种选择似乎是在你的程序参数s的目的，但你永远不要使用它。

你的程序将返回错误的结果为各种各样的树木，其中

N 
/
1

（直径1，但你的函数将返回2）

2 
/\ 
1 3

（直径3，但您的功能将返回2）

（直径4，但您的功能将返回3）

N 
/\ 
N 4 
/\ 
    3 5 
//
2 6 
\ \ 
    1 7

（直径7，但你的函数将返回5）

[在各图中，沿测量所述树的直径的路径中的节点的编号，和所有其他节点被指定“N”。]

事实上，你的函数返回高度，计算在节点中，而不是直径。看起来在有利的情况下，它可能会在s中记录直径，但不一致。

来源

2015-10-05 21:26:28

如果1节点树的高度为0，那么我认为该max表达式中的第三项应该使用常数2而不是1 - 至少使用*“通常”意思是“直径”边缘。由于OP给出的“节点数量之间”的定义，目前还不清楚是否应该计算内部节点（在这种情况下1是正确的）还是所有节点（在这种情况下应该是3）。 –

@j_random_hacker，我澄清了公式中使用的假设和定义。对于它的价值，我更喜欢通过节点而不是边来计算树高，因为这对于零节点和单节点树会产生不同的高度。对于这个问题，这也是一个更方便的定义，并且与给定的直径定义一致。 –

@ John Bollinger您能否给我提供一个上述方法失败的测试用例？ okk你可以按照层次顺序给它的节点值，如果没有孩子，那么简单地把它作为-1。 – sb15

二叉树的直径

回答

相关问题