简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
首頁 > 資料庫 > mysql教程 > 主體

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

WBOY
發布： 2016-06-07 15:10:05
原創
1653 人瀏覽過

题目： 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是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;
	}
}
登入後複製


 

相關標籤：
定義 最大 節點 距離
來源：php.cn
上一篇：SQL Server 有关 索引和视图的简单介绍 下一篇：Linux下静默安装Oracle
本網站聲明
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
作者最新文章
最新問題
子窗口操作父窗口，輸出沒反應 前兩句可執行，最後一句沒辦法應
來自於 2024-04-19 15:37:47
0
1
1361
PHP數組從URL參數中取得的行為不如預期 我有一個包含類別ID的URL參數，我想將其視為一個數組，如下所示：http://example.com?cat[]=3,9,13在PHP中，我使用它從URL參數取得數組：$catI...
來自於 2024-04-06 22:09:02
0
1
1428
透過新增 Width 屬性將內容向左移動 我已經為主體提供了邊距。主要{左邊緣：200px;右邊距：200px；文本對齊：居中}由於我想以兩行而不是一行顯示文本，因此我在樣式中添加了width屬性。 .p{字體大小：12p...
來自於 2024-04-06 22:01:35
0
3
816
傳回值中變數的格式是什麼？ 我是php的新學習者。我發現有一段程式碼：if($x<time()){return[false,'error'];}邏輯或變數並不重要，但我不明白[false,'error'...
來自於 2024-04-06 21:55:20
0
1
778
頁面突然無法拉動 css 或 bootstrap 所以我正在開發一個頁面，我昨天做了一部分，效果很好，今天我繼續做剩下的部分，一切都很好。當我嘗試將其作為普通html頁面打開時，CSS或BOOTSTRAP不起作用，僅顯示頁面文本，...
來自於 2024-04-06 21:58:04
0
1
800
相關專題
更多>
熱門推薦
熱門教學
更多>
相關教學
熱門推薦
最新課程
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網：公益線上PHP培訓，幫助PHP學習者快速成長！