欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树——二叉树任意两个节点之间路径的最大长度

程序员文章站 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
题目来自:牛客网