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

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

程序员文章站 2022-05-16 20:46:09
...

题目： 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是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
  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. 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 "任意两个节点间的最大距离为:"
  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 




 


思路二：


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


 


代码如下：










[cpp] 
view plaincopyprint?



    

  1. int g_nMaxLeft = 0;  
    2. 

  2. void MaxDistance_2(S_TreeNode *psRoot)  
    3. 

  3. {  
    4. 

  4.     // 遍历到叶子节点，返回  
    5. 

  5.     if (NULL == psRoot)  
    6. 

  6.         return;  
    7. 

  7.   
    8. 

  8.     // 如果左子树为空，那么该节点的左边最长距离为0  
    9. 

  9.     if (psRoot->psLeft == NULL)  
    10. 

  10.     {  
    11. 

  11.         psRoot->nMaxLeft = 0;  
    12. 

  12.     }  
    13. 

  13.   
    14. 

  14.     // 如果右子树为空，那么该节点的右边最长距离为0  
    15. 

  15.     if (psRoot->psRight == NULL)  
    16. 

  16.     {  
    17. 

  17.         psRoot -> nMaxRight = 0;  
    18. 

  18.     }  
    19. 

  19.   
    20. 

  20.     // 如果左子树不为空，递归寻找左子树最长距离  
    21. 

  21.     if (psRoot->psLeft != NULL)  
    22. 

  22.     {  
    23. 

  23.         MaxDistance_2(psRoot->psLeft);  
    24. 

  24.     }  
    25. 

  25.   
    26. 

  26.     // 如果右子树不为空，递归寻找右子树最长距离  
    27. 

  27.     if (psRoot->psRight != NULL)  
    28. 

  28.     {  
    29. 

  29.         MaxDistance_2(psRoot->psRight);  
    30. 

  30.     }  
    31. 

  31.   
    32. 

  32.     // 计算左子树最长节点距离  
    33. 

  33.     if (psRoot->psLeft != NULL)  
    34. 

  34.     {  
    35. 

  35.         int nTempMax = 0;  
    36. 

  36.         if (psRoot->psLeft->nMaxLeft > psRoot->psLeft->nMaxRight)  
    37. 

  37.         {  
    38. 

  38.             nTempMax = psRoot->psLeft->nMaxLeft;  
    39. 

  39.         }  
    40. 

  40.         else  
    41. 

  41.         {  
    42. 

  42.             nTempMax = psRoot->psLeft->nMaxRight;  
    43. 

  43.         }  
    44. 

  44.         psRoot->nMaxLeft = nTempMax + 1;  
    45. 

  45.     }  
    46. 

  46.   
    47. 

  47.     // 计算右子树最长节点距离  
    48. 

  48.     if (psRoot->psRight != NULL)  
    49. 

  49.     {  
    50. 

  50.         int nTempMax = 0;  
    51. 

  51.         if(psRoot->psRight->nMaxLeft > psRoot->psRight->nMaxRight)  
    52. 

  52.         {  
    53. 

  53.             nTempMax = psRoot->psRight->nMaxLeft;  
    54. 

  54.         }  
    55. 

  55.         else  
    56. 

  56.         {  
    57. 

  57.             nTempMax = psRoot->psRight->nMaxRight;  
    58. 

  58.         }  
    59. 

  59.         psRoot->nMaxRight = nTempMax + 1;  
    60. 

  60.     }  
    61. 

  61.   
    62. 

  62.     // 更新最长距离  
    63. 

  63.     if (psRoot->nMaxLeft + psRoot->nMaxRight > g_nMaxLeft)  
    64. 

  64.     {  
    65. 

  65.         g_nMaxLeft = psRoot->nMaxLeft + psRoot->nMaxRight;  
    66. 

  66.     }  
    67. 

  67. }  
    68. 



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;
	}
}
相关标签： 一个 二叉 树中 任意 两个 节点 间的 最大 距离 定义

上一篇： Photoshop调出沙漠中的仙境效果

下一篇： mysql 向数据库中插入一项数据

推荐阅读