求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义-mysql教程-PHP中文網

首頁

資料庫

mysql教程

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 07, 2016 pm 03:10 PM

定義最大節點距離

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

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

优化时间空间杂度。

思路一：

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

代码如下：

[cpp] view plaincopyprint?

/*-----------------------------
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
{
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 "任意两个节点间的最大距离为:"
return 0;
}

/*-----------------------------
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;
	}
}

登入後複製

本網站聲明

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

熱AI工具

熱工具

熱門話題

gmail信箱登陸入口在哪裡

7733

Java教學

1643

CakePHP 教程

1397

Laravel 教程

1290

PHP教程

1233

Related knowledge

C程式計算3D空間中三個點之間的距離 Aug 29, 2023 pm 12:41 PM

給定一個三維平面，因此有三個座標，任務是找到給定點之間的距離並顯示結果。在三維平面上，有三個座標軸，x軸的座標為（x1，y1，z1），y軸的座標為（x2，y2，z2），z軸的座標為（x3，y3，z）。計算它們之間的距離有一個直接的公式如下所示$$\sqrt{\lgroupx2-x1\rgroup^{2}+\lgroupy2-y1\rgroup^{2}+\lgroupz2-z1\rgroup^{2 }}$$下面是表示三個不同座標軸及其座標的圖示下面所使用的方法如下−輸入座標（x1，

iOS 17：如何在待機模式下變更iPhone時鐘樣式 Sep 10, 2023 pm 09:21 PM

待機是一種鎖定螢幕模式，當iPhone插入充電器並以水平（或橫向）方向定位時啟動。它由三個不同的螢幕組成，其中一個是全螢幕時間顯示。繼續閱讀以了解如何變更時鐘的樣式。 StandBy的第三個畫面顯示各種主題的時間和日期，您可以垂直滑動。某些主題也會顯示其他訊息，例如溫度或下一個鬧鐘。如果您按住任何時鐘，則可以在不同的主題之間切換，包括數位、類比、世界、太陽能和浮動。 Float以可自訂的顏色以大氣泡數字顯示時間，Solar具有更多標準字體，具有不同顏色的太陽耀斑設計，而World則透過突出顯示世界地

機器學習基礎之數字上的距離：點在空間中的距離 Apr 11, 2023 pm 11:40 PM

本文轉載自微信公眾號「活在資訊時代」，作者活在資訊時代。轉載本文請聯絡活在資訊時代公眾號。在機器學習中，一個基礎的概念就是如何判斷兩個樣本之間的差異，以便能夠評估兩個樣本之間的相似性和類別等資訊。而判斷這種相似性的測量就是兩個樣本在特徵空間內的距離。根據資料特徵的不同，度量方法有很多種。一般而言，對兩個資料樣本x，y，定義一個函數d（x，y），如果定義其為兩個樣本之間的距離，那麼d（x，y）則需要滿足以下幾個基本性質：非負性：d（x，y）>=0同一性：d（x，y）=0 ⇔ x=y對

短視頻的定義是什麼 Dec 23, 2020 pm 02:56 PM

短影片的定義是指在各種新媒體平台上播放的、適合在移動狀態和短時休閒狀態下觀看的、高頻推送的視頻內容，一般是在互聯網新媒體上傳播的時長在5分鐘以內的影片；內容融合了技能分享、幽默搞怪、時尚潮流、社會熱點、街頭採訪、公益教育、廣告創意、商業客製化等主題。短影片有著生產流程簡單、製作門檻低、參與性強等特質。

MySQL 複合主鍵的定義與作用 Mar 15, 2024 pm 05:18 PM

MySQL中的複合主鍵是指表中由多個欄位組合而成的主鍵，用來唯一標識每筆記錄。與單一主鍵不同的是，複合主鍵由多個欄位的值組合在一起形成。在建立表格的時候，可以透過指定多個欄位為主鍵來定義複合主鍵。為了示範複合主鍵的定義與作用，我們先建立一個名為users的表，其中包含了id、username和email這三個字段，其中id是自增主鍵，user

什麼是Discuz？ Discuz的定義與功能介紹 Mar 03, 2024 am 10:33 AM

《探索Discuz：定義、功能及程式碼範例》隨著網路的快速發展，社群論壇已成為人們獲取資訊、交流觀點的重要平台。在眾多的社群論壇系統中，Discuz作為國內較知名的一種開源論壇軟體，備受廣大網站開發者和管理員的青睞。那麼，什麼是Discuz？它又有哪些功能，能為我們的網站提供怎樣的幫助呢？本文將對Discuz進行詳細介紹，並附上具體的程式碼範例，幫助讀者更

如何在 Microsoft Word 中製作自訂邊框 Nov 18, 2023 pm 11:17 PM

想讓你的學校計畫的頭版看起來令人興奮嗎？沒有什麼比工作簿首頁上的漂亮、優雅的邊框更能使其從其他提交中脫穎而出了。但是，MicrosoftWord中的標準單行邊框已經變得非常明顯和無聊。因此，我們展示了在MicrosoftWord文件中建立和使用自訂邊框的步驟。如何在MicrosoftWord中製作自訂邊框建立自訂邊框非常容易。但是，您將需要一個邊界。步驟1–下載自訂邊框網路上有大量的免費邊界。我們已經下載了一個這樣的邊框。步驟1–在Internet上搜尋自訂邊框。或者，您可以轉到剪貼

如何在iOS 17上啟用和使用螢幕距離 Jun 29, 2023 pm 01:37 PM

在其年度開發者大會上，蘋果推出了下一代作業系統來為其設備套件提供支援。像往常一樣，iOS17是所有主要變化的核心，具有即時語音郵件、訊息轉錄、即時貼紙、待機模式、全螢幕即時活動、互動式小部件等功能。在這些新增功能中脫穎而出的功能之一是「螢幕距離」。這是一項以健康為中心的功能，專注於防止iPhone螢幕上的眼睛疲勞和近視。在這篇文章中，我們將解釋什麼是螢幕距離以及如何在iOS17中啟用它。什麼是iOS17上的螢幕距離？作為iOS17推出的新健康功能的一部分，Apple提供了螢幕距離功能，以幫助用戶預先

See all articles

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

熱AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

Video Face Swap

熱門文章

熱工具

記事本++7.3.1

SublimeText3漢化版

禪工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

熱門話題