• 欢迎访问搞代码网站，推荐使用最新版火狐浏览器和Chrome浏览器访问本网站！
  • 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏搞代码吧
> 数据库 > mysql > 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义

求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义

mysql 搞代码 4年前 (2022-01-09) 16次浏览 已收录 0个评论

题目： 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2， 优化时间空间杂度。 思路一： 计算一个二叉树的最大距离有两个情况: 情况A: 路径经过左子

题目：
求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，

优化时间空间杂度。

思路一：

计算一个二叉树的最大距离有两个情况:
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
首先算出经过根节点的最大路径的距离，其实就是左右子树的深度和；然后分别算出左子树和右子树的最大距离，三者比较，最大值就是当前二叉树的最大距离了。

代码如下：

[cpp] view plaincopyprint?

  1. /*—————————–
  2. Copyright by yuucyf. 2011.09.02
  3. ——————————*/
  4. #include “stdafx.h”
  5. #include
  6. #include
  7. using namespace std;
  9. typedef struct tagSBTreeNode
  10. {
  11. tagSBTreeNode *psLeft;
  12. tagSBTreeNode *psRight;
  13. int nValue;
  15. int nMaxLeft;
  16. int nMaxRight;
  18. tagSBTreeNode()
  19. {
  20. psLeft = psRight = NULL;
  21. nValue = 0;
  22. nMaxLeft = nMaxRight = 0;
  23. }
  24. }S_TreeNode;
  27. void AddTreeNode(S_TreeNode *&psTreeNode, int nValue)
  28. {
  29. if (NULL == psTreeNode)
  30. {
  31. psTreeNode = new S_TreeNode;
  32. assert(NULL != psTreeNode);
  33. psTreeNode->nValue = nValue;
  34. }
  35. else if (psTreeNode->nValue < nValue)
  36. {
  37. AddTreeNode(psTreeNode->psRight, nValue);
  38. }
  39. else
  40. AddTreeNode(psTreeNode->psLeft, nValue);
  41. }
  43. int MaxDepth(const S_TreeNode *psTreeNode)
  44. {
  45. int nDepth = 0;
  46. if (NULL != psTreeNode)
  47. {
  48. int nLeftDepth = MaxDepth(psTreeNode->psLeft);
  49. int nRightDepth = MaxDepth(psTreeNode->psRight);
  50. nDepth = (nLeftDepth > nRightDepth) ? nLeftDepth : nRightDepth;
  51. nDepth++;
  52. }
  54. return nDepth;
  55. }
  57. int MaxDistance(const S_TreeNode *psRootNode)
  58. {
  59. int nDistance = 0;
  60. if (NULL != psRootNode)
  61. {
  62. nDistance = MaxDepth(psRootNode->psLeft) + MaxDepth(psRootNode->psRight);
  63. int nLeftDistance = MaxDistance(psRootNode->psLeft);
  64. int nRightDistance= MaxDistance(psRootNode->psRight);
  66. nDistance = (nLeftDistance > nDistance) ? nLeftDistance : nDistance;
  67. nDistance = (nRightDistance > nDistance) ? nRightDistance : nDistance;
  68. }
  70. return nDistance;
  71. }
  76. int _tmain(int argc, _TCHAR* argv[])
  77. {
  78. 本文来源gao($daima.com搞@代@#码(网5 S_TreeNode *psRoot = NULL;
  79. AddTreeNode(psRoot, 9);
  80. AddTreeNode(psRoot, 6);
  81. AddTreeNode(psRoot, 4);
  82. AddTreeNode(psRoot, 8);
  83. AddTreeNode(psRoot, 7);
  84. AddTreeNode(psRoot, 15);
  85. AddTreeNode(psRoot, 13);
  86. AddTreeNode(psRoot, 16);
  87. AddTreeNode(psRoot, 18);
  89. cout << “任意两个节点间的最大距离为:” << MaxDistance(psRoot) << endl;
  91. return 0;
  92. } 
/*-----------------------------Copyright by yuucyf. 2011.09.02------------------------------*/#include "stdafx.h"#include #include using namespace std;typedef struct tagSBTreeNode{	tagSBTreeNode *psLeft;	tagSBTreeNode *psRight;	int	nValue;	int nMaxLeft;	int nMaxRight;	tagSBTreeNode()	{		psLeft = psRight = NULL;		nValue = 0;		nMaxLeft = nMaxRight = 0;	}}S_TreeNode;void AddTreeNode(S_TreeNode *&psTreeNode, int nValue){	if (NULL == psTreeNode)	{		psTreeNode = new S_TreeNode;		assert(NULL != psTreeNode);		psTreeNode->nValue = nValue;	}	else if (psTreeNode->nValue psRight, nValue);	}	else		AddTreeNode(psTreeNode->psLeft, nValue);}int MaxDepth(const S_TreeNode *psTreeNode){	int nDepth = 0;	if (NULL != psTreeNode)	{		int nLeftDepth = MaxDepth(psTreeNode->psLeft);		int nRightDepth = MaxDepth(psTreeNode->psRight);		nDepth = (nLeftDepth > nRightDepth) ? nLeftDepth : nRightDepth;		nDepth++;	}	return nDepth;}int MaxDistance(const S_TreeNode *psRootNode){	int nDistance = 0;	if (NULL != psRootNode)	{		nDistance = MaxDepth(psRootNode->psLeft) + MaxDepth(psRootNode->psRight);		int nLeftDistance = MaxDistance(psRootNode->psLeft);		int nRightDistance= MaxDistance(psRootNode->psRight);				nDistance = (nLeftDistance > nDistance) ? nLeftDistance : nDistance;		nDistance = (nRightDistance > nDistance) ? nRightDistance : nDistance;	}		return nDistance;}int _tmain(int argc, _TCHAR* argv[]){	S_TreeNode *psRoot = NULL;	AddTreeNode(psRoot, 9);	AddTreeNode(psRoot, 6);	AddTreeNode(psRoot, 4);	AddTreeNode(psRoot, 8);	AddTreeNode(psRoot, 7);	AddTreeNode(psRoot, 15);	AddTreeNode(psRoot, 13);	AddTreeNode(psRoot, 16);	AddTreeNode(psRoot, 18);	cout << "任意两个节点间的最大距离为:" << MaxDistance(psRoot) << endl;	return 0;}

思路二：

思路一不是效率最高的，因为在计算二叉树的深度的时候存在重复计算。但应该是可读性比较好的，同时也没有改变原有二叉树的结构和使用额外的全局变量。这里之间给出代码，因为代码的注释已经写的非常详细了。

代码如下：

[cpp] view plaincopyprint?

  1. int g_nMaxLeft = 0;
  2. void MaxDistance_2(S_TreeNode *psRoot)
  3. {
  4. // 遍历到叶子节点，返回
  5. if (NULL == psRoot)
  6. return;
  8. // 如果左子树为空，那么该节点的左边最长距离为0
  9. if (psRoot->psLeft == NULL)
  10. {
  11. psRoot->nMaxLeft = 0;
  12. }
  14. // 如果右子树为空，那么该节点的右边最长距离为0
  15. if (psRoot->psRight == NULL)
  16. {
  17. psRoot -> nMaxRight = 0;
  18. }
  20. // 如果左子树不为空，递归寻找左子树最长距离
  21. if (psRoot->psLeft != NULL)
  22. {
  23. MaxDistance_2(psRoot->psLeft);
  24. }
  26. // 如果右子树不为空，递归寻找右子树最长距离
  27. if (psRoot->psRight != NULL)
  28. {
  29. MaxDistance_2(psRoot->psRight);
  30. }
  32. // 计算左子树最长节点距离
  33. if (psRoot->psLeft != NULL)
  34. {
  35. int nTempMax = 0;
  36. if (psRoot->psLeft->nMaxLeft > psRoot->psLeft->nMaxRight)
  37. {
  38. nTempMax = psRoot->psLeft->nMaxLeft;
  39. }
  40. else
  41. {
  42. nTempMax = psRoot->psLeft->nMaxRight;
  43. }
  44. psRoot->nMaxLeft = nTempMax + 1;
  45. }
  47. // 计算右子树最长节点距离
  48. if (psRoot->psRight != NULL)
  49. {
  50. int nTempMax = 0;
  51. if(psRoot->psRight->nMaxLeft > psRoot->psRight->nMaxRight)
  52. {
  53. nTempMax = psRoot->psRight->nMaxLeft;
  54. }
  55. else
  56. {
  57. nTempMax = psRoot->psRight->nMaxRight;
  58. }
  59. psRoot->nMaxRight = nTempMax + 1;
  60. }
  62. // 更新最长距离
  63. if (psRoot->nMaxLeft + psRoot->nMaxRight > g_nMaxLeft)
  64. {
  65. g_nMaxLeft = psRoot->nMaxLeft + psRoot->nMaxRight;
  66. }
  67. } 
int g_nMaxLeft = 0;void MaxDistance_2(S_TreeNode *psRoot){	// 遍历到叶子节点，返回	if (NULL == psRoot)		return;	// 如果左子树为空，那么该节点的左边最长距离为0	if (psRoot->psLeft == NULL)	{		psRoot->nMaxLeft = 0;	}	// 如果右子树为空，那么该节点的右边最长距离为0	if (psRoot->psRight == NULL)	{		psRoot -> nMaxRight = 0;	}	// 如果左子树不为空，递归寻找左子树最长距离	if (psRoot->psLeft != NULL)	{		MaxDistance_2(psRoot->psLeft);	}	// 如果右子树不为空，递归寻找右子树最长距离	if (psRoot->psRight != NULL)	{		MaxDistance_2(psRoot->psRight);	}	// 计算左子树最长节点距离	if (psRoot->psLeft != NULL)	{		int nTempMax = 0;		if (psRoot->psLeft->nMaxLeft > psRoot->psLeft->nMaxRight)		{			nTempMax = psRoot->psLeft->nMaxLeft;		}		else		{			nTempMax = psRoot->psLeft->nMaxRight;		}		psRoot->nMaxLeft = nTempMax + 1;	}	// 计算右子树最长节点距离	if (psRoot->psRight != NULL)	{		int nTempMax = 0;		if(psRoot->psRight->nMaxLeft > psRoot->psRight->nMaxRight)		{			nTempMax = psRoot->psRight->nMaxLeft;		}		else		{			nTempMax = psRoot->psRight->nMaxRight;		}		psRoot->nMaxRight = nTempMax + 1;	}	// 更新最长距离	if (psRoot->nMaxLeft + psRoot->nMaxRight > g_nMaxLeft)	{		g_nMaxLeft = psRoot->nMaxLeft + psRoot->nMaxRight;	}}
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]‍，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义

喜欢 (0)赏
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi，您需要填写昵称和邮箱！

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址