《編程之美: 求二叉樹中節(jié)點的最大距離》的另一個解法

昨天花了一個晚上為《編程之美》，在豆瓣寫了一篇書評《遲來的書評和感想──給喜愛編程的朋友》。書評就不轉(zhuǎn)載到這里了，取而代之，在這里介紹書里其中一條問題的另一個解法。這個解法比較簡短易讀及降低了空間復(fù)雜度，或者可以說覺得比較「美」吧。

問題定義

如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。寫一個程序求一棵二叉樹中相距最遠的兩個節(jié)點之間的距離。

書上的解法

書中對這個問題的分析是很清楚的，我嘗試用自己的方式簡短覆述。

計算一個二叉樹的最大距離有兩個情況:

情況A: 路徑經(jīng)過左子樹的最深節(jié)點，通過根節(jié)點，再到右子樹的最深節(jié)點。情況B: 路徑不穿過根節(jié)點，而是左子樹或右子樹的最大距離路徑，取其大者。

只需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離。

我也想不到更好的分析方法。

但接著，原文的實現(xiàn)就不如上面的清楚 (源碼可從這里下載):

//?數(shù)據(jù)結(jié)構(gòu)定義
struct?NODE
{
	NODE*?pLeft;???????	//?左子樹
	NODE*?pRight;??????	//?右子樹
	int?nMaxLeft;??????	//?左子樹中的最長距離
	int?nMaxRight;?????	//?右子樹中的最長距離
	char?chValue;????	//?該節(jié)點的值
};

int?nMaxLen?=?0;

//?尋找樹中最長的兩段距離
void?FindMaxLen(NODE*?pRoot)
{
	//?遍歷到葉子節(jié)點，返回
	if(pRoot?==?NULL)
	{
		return;
	}

	//?如果左子樹為空，那么該節(jié)點的左邊最長距離為0
	if(pRoot?->?pLeft?==?NULL)
	{
		pRoot?->?nMaxLeft?=?0;?
	}

	//?如果右子樹為空，那么該節(jié)點的右邊最長距離為0
	if(pRoot?->?pRight?==?NULL)
	{
		pRoot?->?nMaxRight?=?0;
	}

	//?如果左子樹不為空，遞歸尋找左子樹最長距離
	if(pRoot?->?pLeft?!=?NULL)
	{
		FindMaxLen(pRoot?->?pLeft);
	}

	//?如果右子樹不為空，遞歸尋找右子樹最長距離
	if(pRoot?->?pRight?!=?NULL)
	{
		FindMaxLen(pRoot?->?pRight);
	}

	//?計算左子樹最長節(jié)點距離
	if(pRoot?->?pLeft?!=?NULL)
	{
		int?nTempMax?=?0;
		if(pRoot?->?pLeft?->?nMaxLeft?>?pRoot?->?pLeft?->?nMaxRight)
		{
			nTempMax?=?pRoot?->?pLeft?->?nMaxLeft;
		}
		else
		{
			nTempMax?=?pRoot?->?pLeft?->?nMaxRight;
		}
		pRoot?->?nMaxLeft?=?nTempMax?+?1;
	}

	//?計算右子樹最長節(jié)點距離
	if(pRoot?->?pRight?!=?NULL)
	{
		int?nTempMax?=?0;
		if(pRoot?->?pRight?->?nMaxLeft?>?pRoot?->?pRight?->?nMaxRight)
		{
			nTempMax?=?pRoot?->?pRight?->?nMaxLeft;
		}
		else
		{
			nTempMax?=?pRoot?->?pRight?->?nMaxRight;
		}
		pRoot?->?nMaxRight?=?nTempMax?+?1;
	}

	//?更新最長距離
	if(pRoot?->?nMaxLeft?+?pRoot?->?nMaxRight?>?nMaxLen)
	{
		nMaxLen?=?pRoot?->?nMaxLeft?+?pRoot?->?nMaxRight;
	}
}

這段代碼有幾個缺點:

算法加入了侵入式(intrusive)的資料nMaxLeft, nMaxRight使用了全局變量 nMaxLen。每次使用要額外初始化。而且就算是不同的獨立資料，也不能在多個線程使用這個函數(shù)邏輯比較復(fù)雜，也有許多 NULL 相關(guān)的條件測試。我的嘗試

我認為這個問題的核心是，情況A?及 B 需要不同的信息: A 需要子樹的最大深度，B 需要子樹的最大距離。只要函數(shù)能在一個節(jié)點同時計算及傳回這兩個信息，代碼就可以很簡單:

#includeusing?namespace?std;

struct?NODE
{
	NODE?*pLeft;
	NODE?*pRight;
};

struct?RESULT
{
	int?nMaxDistance;
	int?nMaxDepth;
};

RESULT?GetMaximumDistance(NODE*?root)
{
	if?(!root)
	{
		RESULT?empty?=?{?0,?-1?};	//?trick:?nMaxDepth?is?-1?and?then?caller?will?plus?1?to?balance?it?as?zero.
		return?empty;
	}

	RESULT?lhs?=?GetMaximumDistance(root->pLeft);
	RESULT?rhs?=?GetMaximumDistance(root->pRight);

	RESULT?result;
	result.nMaxDepth?=?max(lhs.nMaxDepth?+?1,?rhs.nMaxDepth?+?1);
	result.nMaxDistance?=?max(max(lhs.nMaxDistance,?rhs.nMaxDistance),?lhs.nMaxDepth?+?rhs.nMaxDepth?+?2);
	return?result;
}

計算 result 的代碼很清楚；nMaxDepth 就是左子樹和右子樹的深度加1；nMaxDistance 則取 A 和 B 情況的最大值。

為了減少 NULL 的條件測試，進入函數(shù)時，如果節(jié)點為 NULL，會傳回一個 empty 變量。比較奇怪的是 empty.nMaxDepth = -1，目的是讓調(diào)用方 +1 后，把當(dāng)前的不存在的 (NULL) 子樹當(dāng)成最大深度為 0。

除了提高了可讀性，這個解法的另一個優(yōu)點是減少了 O(節(jié)點數(shù)目) 大小的侵入式資料，而改為使用 O(樹的最大深度) 大小的?？臻g。這個設(shè)計使函數(shù)完全沒有副作用(side effect)。

測試代碼

以下也提供測試代碼給讀者參考 (頁數(shù)是根據(jù)第7次印刷，節(jié)點是由上至下、左至右編號):

void?Link(NODE*?nodes,?int?parent,?int?left,?int?right)
{
	if?(left?!=?-1)
		nodes[parent].pLeft?=?&nodes[left];?

	if?(right?!=?-1)
		nodes[parent].pRight?=?&nodes[right];
}

void?main()
{
	//?P.?241?Graph?3-12
	NODE?test1[9]?=?{?0?};
	Link(test1,?0,?1,?2);
	Link(test1,?1,?3,?4);
	Link(test1,?2,?5,?6);
	Link(test1,?3,?7,?-1);
	Link(test1,?5,?-1,?8);
	cout?<<?"test1:?"?<<?GetMaximumDistance(&test1[0]).nMaxDistance?<<?endl;

	//?P.?242?Graph?3-13?left
	NODE?test2[4]?=?{?0?};
	Link(test2,?0,?1,?2);
	Link(test2,?1,?3,?-1);
	cout?<<?"test2:?"?<<?GetMaximumDistance(&test2[0]).nMaxDistance?<<?endl;

	//?P.?242?Graph?3-13?right
	NODE?test3[9]?=?{?0?};
	Link(test3,?0,?-1,?1);
	Link(test3,?1,?2,?3);
	Link(test3,?2,?4,?-1);
	Link(test3,?3,?5,?6);
	Link(test3,?4,?7,?-1);
	Link(test3,?5,?-1,?8);
	cout?<<?"test3:?"?<<?GetMaximumDistance(&test3[0]).nMaxDistance?<<?endl;

	//?P.?242?Graph?3-14
	//?Same?as?Graph?3-2,?not?test

	//?P.?243?Graph?3-15
	NODE?test4[9]?=?{?0?};
	Link(test4,?0,?1,?2);
	Link(test4,?1,?3,?4);
	Link(test4,?3,?5,?6);
	Link(test4,?5,?7,?-1);
	Link(test4,?6,?-1,?8);
	cout?<<?"test4:?"?<<?GetMaximumDistance(&test4[0]).nMaxDistance?<<?endl;
}