suchen

Heim >Datenbank >MySQL-Tutorial >求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义

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

WBOY
WBOYOriginal
2016-06-07 15:10:051670Durchsuche

题目： 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是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;  
  8.   
  9. typedef struct tagSBTreeNode  
  10. {  
  11.     tagSBTreeNode *psLeft;  
  12.     tagSBTreeNode *psRight;  
  13.     int nValue;  
  14.   
  15.     int nMaxLeft;  
  16.     int nMaxRight;  
  17.   
  18.     tagSBTreeNode()  
  19.     {  
  20.         psLeft = psRight = NULL;  
  21.         nValue = 0;  
  22.         nMaxLeft = nMaxRight = 0;  
  23.     }  
  24. }S_TreeNode;  
  25.   
  26.   
  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. }  
  42.   
  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.     }  
  53.   
  54.     return nDepth;  
  55. }  
  56.   
  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);  
  65.           
  66.         nDistance = (nLeftDistance > nDistance) ? nLeftDistance : nDistance;  
  67.         nDistance = (nRightDistance > nDistance) ? nRightDistance : nDistance;  
  68.     }  
  69.       
  70.     return nDistance;  
  71. }  
  72.   
  73.   
  74.   
  75.   
  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);  
  88.   
  89.     cout "任意两个节点间的最大距离为:" 
  90.   
  91.     return 0;  
  92. }  
/*-----------------------------
Copyright by yuucyf. 2011.09.02
------------------------------*/
#include "stdafx.h"
#include <iostream>
#include <assert.h>
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 
<p><br>
</p>
<p> </p>
<p><span>思路二：</span></p>
<p>思路一不是效率最高的，因为在计算二叉树的深度的时候存在重复计算。但应该是可读性比较好的，同时也没有改变原有二叉树的结构和使用额外的全局变量。这里之间给出代码，因为代码的注释已经写的非常详细了。</p>
<p> </p>
<p><span>代码如下：</span></p>
<p>
</p>
<p>
</p>
<p><strong>[cpp]</strong> 
view plaincopyprint?</p>

<ol>
<li><span><span>int</span><span> g_nMaxLeft = 0;  </span></span></li>
<li><span><span>void</span><span> MaxDistance_2(S_TreeNode *psRoot)  </span></span></li>
<li><span>{  </span></li>
<li><span>    <span>// 遍历到叶子节点，返回</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (NULL == psRoot)  </span></span></li>
<li><span>        <span>return</span><span>;  </span></span></li>
<li><span>  </span></li>
<li><span>    <span>// 如果左子树为空，那么该节点的左边最长距离为0</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (psRoot->psLeft == NULL)  </span></span></li>
<li><span>    {  </span></li>
<li><span>        psRoot->nMaxLeft = 0;  </span></li>
<li><span>    }  </span></li>
<li><span>  </span></li>
<li><span>    <span>// 如果右子树为空，那么该节点的右边最长距离为0</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (psRoot->psRight == NULL)  </span></span></li>
<li><span>    {  </span></li>
<li><span>        psRoot -> nMaxRight = 0;  </span></li>
<li><span>    }  </span></li>
<li><span>  </span></li>
<li><span>    <span>// 如果左子树不为空，递归寻找左子树最长距离</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (psRoot->psLeft != NULL)  </span></span></li>
<li><span>    {  </span></li>
<li><span>        MaxDistance_2(psRoot->psLeft);  </span></li>
<li><span>    }  </span></li>
<li><span>  </span></li>
<li><span>    <span>// 如果右子树不为空，递归寻找右子树最长距离</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (psRoot->psRight != NULL)  </span></span></li>
<li><span>    {  </span></li>
<li><span>        MaxDistance_2(psRoot->psRight);  </span></li>
<li><span>    }  </span></li>
<li><span>  </span></li>
<li><span>    <span>// 计算左子树最长节点距离</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (psRoot->psLeft != NULL)  </span></span></li>
<li><span>    {  </span></li>
<li><span>        <span>int</span><span> nTempMax = 0;  </span></span></li>
<li><span>        <span>if</span><span> (psRoot->psLeft->nMaxLeft > psRoot->psLeft->nMaxRight)  </span></span></li>
<li><span>        {  </span></li>
<li><span>            nTempMax = psRoot->psLeft->nMaxLeft;  </span></li>
<li><span>        }  </span></li>
<li><span>        <span>else</span><span>  </span></span></li>
<li><span>        {  </span></li>
<li><span>            nTempMax = psRoot->psLeft->nMaxRight;  </span></li>
<li><span>        }  </span></li>
<li><span>        psRoot->nMaxLeft = nTempMax + 1;  </span></li>
<li><span>    }  </span></li>
<li><span>  </span></li>
<li><span>    <span>// 计算右子树最长节点距离</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (psRoot->psRight != NULL)  </span></span></li>
<li><span>    {  </span></li>
<li><span>        <span>int</span><span> nTempMax = 0;  </span></span></li>
<li><span>        <span>if</span><span>(psRoot->psRight->nMaxLeft > psRoot->psRight->nMaxRight)  </span></span></li>
<li><span>        {  </span></li>
<li><span>            nTempMax = psRoot->psRight->nMaxLeft;  </span></li>
<li><span>        }  </span></li>
<li><span>        <span>else</span><span>  </span></span></li>
<li><span>        {  </span></li>
<li><span>            nTempMax = psRoot->psRight->nMaxRight;  </span></li>
<li><span>        }  </span></li>
<li><span>        psRoot->nMaxRight = nTempMax + 1;  </span></li>
<li><span>    }  </span></li>
<li><span>  </span></li>
<li><span>    <span>// 更新最长距离</span><span>  </span></span></li>
<li><span>    <span>if</span><span> (psRoot->nMaxLeft + psRoot->nMaxRight > g_nMaxLeft)  </span></span></li>
<li><span>    {  </span></li>
<li><span>        g_nMaxLeft = psRoot->nMaxLeft + psRoot->nMaxRight;  </span></li>
<li><span>    }  </span></li>
<li><span>}  </span></li>
</ol>

<pre class="brush:php;toolbar:false">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;
	}
}


 

Stellungnahme：
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel：SQL Server 有关 索引和视图的简单介绍Nächster Artikel：Linux下静默安装Oracle

In Verbindung stehende Artikel

Mehr sehen