K*****k
发帖数: 430 | 1 定义直径为连通两节点最多的边数
空树和单节点树的直径都是0
直径有可能通过根节点，也可能通过某棵子树的根节点但不通过根节点。
利用经典的求二叉树高度的递归函数，同时保持直径的最大值，就可以了么？
// The initial value of diameter is set to 0
int Depth(Node* root, int& diameter)
{
if (root == NULL)
return 0;
int LDepth = Depth(root->left, diameter);
int RDepth = Depth(root->right, diameter);
if (LDepth + RDepth > diameter)
diameter = LDepth + RDepth;
return max(LDepth + 1, RDepth + 1);
} | s****a
发帖数: 528 | 2 ????
if (LDepth + RDepth + 2 > diameter) | K*****k
发帖数: 430 | 3 空树的高度定义为0，单节点树的高度定义为1， 这里无须加2，画个图就知道了。
【在 s****a 的大作中提到】
: ????
: if (LDepth + RDepth + 2 > diameter)
| f********e
发帖数: 166 | | z****u
发帖数: 104 | 5 链接里的程序是不是有问题？程序如下：
int diameter2(TreeNode t, int* height)
{
int lh = 0, rh = 0;
int leftD = 0, rightD = 0;
if(t == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}
leftD = diameter2(root->left, &lh);
rightD = diameter2(root->right,&rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;
return max(lh + rh + 1, leftD, rightD);
}
return max(lh + rh + 1, leftD, rightD);
应该是
return max(lh + rh + 2, leftD, rightD);
？
【在 f********e 的大作中提到】
: http://tech-queries.blogspot.com/2010/09/diameter-of-tree-in-on
|
|
