
题目介绍:
如果把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两个节点之间的个数。
写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
如下图所示,粗箭头的边表示最长距离,显然最大距离是从A到B,为6。
我的思路:最长路径必然要经过树或者其子树的根节点,所以可以用递归来解决,即把这一问题转化为子树的最大距离。
int max_len = ;//保存二叉树结点的最大距离
int maxDepth(TreeNode* root)
{
if(root!=NULL)
{
int left_len = maxDepth(root->left);//左子树的最大深度
int right_len = maxDepth(root->right);//右子树的最大深度
max_len = max(max_len, left_len+right_len);//最大长度显然等于子树中根节点左右子树最大深度之和
return max(left_len,right_len)+;//返回的深度为根节点左右子树的深度+根节点(1)
}
else
{
return ;
}
}