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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7688字，纯文字阅读大概需要11分钟。

内容图文

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

内容总结

以上是互联网集市为您收集整理的求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义全部内容，希望文章能够帮你解决求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---