寻找一棵树的直径 [英] Finding Diameter of a Tree
问题描述
我已经编写了用于查找二叉树直径的代码.但是我无法弄清楚哪里出了问题.我编写的两个函数及其定义如下:-
I have written code for finding the diameter of binary tree. But I am unable to figure out where is it going wrong . The two functions that I have written and their definition are as follows :-
int btree::diameteroftree(node* leaf)
{
if (leaf==NULL)
return 0;
int lheight = hieghtoftree(leaf->left);
int rheight = hieghtoftree(leaf->right);
int ldiameter = diameteroftree(leaf->left);
int rdiameter = diameteroftree(leaf->right);
return max(lheight + rheight + 1,max(ldiameter,rdiameter));
}
int btree::hieghtoftree(node* leaf)
{
int left=0,right=0;
if(leaf==NULL)
return -1;
else
{
left=hieghtoftree(leaf->left);
right=hieghtoftree(leaf->right);
if(left > right)
return left +1;
else
return right+1;
}
}
我无法弄清楚我在哪里出问题了.有人可以让我知道...
I am unable to figure out where am I going wrong here . Can someone let me know ...
推荐答案
您要返回最长路径上的节点数.因此,您算法中的问题是这一行:
You want to return the number of nodes on the longest path. Therefore, the problem in your algorithm is this line:
return max(lheight + rheight + 1,max(ldiameter,rdiameter));
其中
rootDiameter = lheight + rheight + 1
是从左侧树的最深节点到右侧树的最深节点的路径长度.但是,此计算是不正确的.单个节点返回的高度为0,因此不会被计算在内.您有两种选择:
is the length of the path from the deepest node of the left tree to the deepest node of the right tree. However, this calculation is not correct. A single node returns a height of 0, so it will not be counted. You have two options:
- 更改
hieghtoftree
以返回最深路径上的节点数,而不是跳数" - 总结您的问题
- Change
hieghtoftree
to return the number of nodes on the deepest path and not the number of "hops" - Address this problem in your summation
.
return max(lheight + rheight + 3,max(ldiameter,rdiameter));
这篇关于寻找一棵树的直径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!