树——二叉树任意两个节点之间路径的最大长度
程序员文章站
2024-03-15 12:23:23
...
考察点:树
参考回答:
int maxDist(Tree root) {
//如果树是空的,则返回 0
if(root == NULL)
return 0;
if(root->left != NULL) {
root->lm = maxDist(root->left) + 1;
}
if(root->right != NULL) root->rm = maxDist(root->right) + 1;
//如果以该节点为根的子树中有最大的距离,那就更新最大距离
int sum = root->rm + root->lm;
if(sum > max) {
max = sum;
}
return root->rm > root->lm ? root->rm : root->lm;
}
算法理解:
首先要分清一个概念什么是树的高度,什么是树的深度。
简单来说,对于整棵树来说,最深的叶结点的深度就是树的深度;树根的高度就是树的高度。这样树的高度和深度是相等的。
对于树中相同深度的每个结点来说,它们的高度不一定相同,这取决于每个结点下面的叶结点的深度。
了解了高度与深度的概念。要计算一个树任意两个节点的最大距离,从根节点出发,无非就两种情况。1.一种是最长路径经过根节点,2.另一种是最长路径不经过根节点。
1.对于情况1,左子树的高度加上右子树的高度即为整棵树的最大路径。
2.对于情况2,既然不经过根节点,那就可以再次分为两种情况,2.1整棵树的最大路径是左子树的最大路径,2.2整棵树的最大路径是右子树的最大路径。
而下面的两种情况又可以归结为最初始的求树的最大路径算法,各分为过根节点和不过根节点的两种情况。如此通过递归算法,最终可以求得整棵树的最大路径。
理解参考:
算法理解参考:https://www.2cto.com/kf/201410/340454.html
树的理解参考:https://blog.csdn.net/fanpei_moukoy/article/details/23828603
题目来自:牛客网
上一篇: 判断101-200之间有多少个素数,并输出所有素数。
下一篇: 204.计数质数