<编程之美>经典面试题:求二叉树节点的最大距离(我的解法,最容易理解的版本?)

时间:2023-03-09 21:33:51
<编程之美>经典面试题:求二叉树节点的最大距离(我的解法,最容易理解的版本?)

题目介绍:

如果把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两个节点之间的个数。

写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

如下图所示,粗箭头的边表示最长距离,显然最大距离是从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 ;
}
}