《編程之美: 求二叉樹中節(jié)點(diǎn)的最大距離》的另一個(gè)解法
昨天花了一個(gè)晚上為《編程之美》，在豆瓣寫了一篇書評(píng)《遲來的書評(píng)和感想──給喜愛編程的朋友》。書評(píng)就不轉(zhuǎn)載到這里了，取而代之，在這里介紹書里其中一條問題的另一個(gè)解法。這個(gè)解法比較簡(jiǎn)短易讀及降低了空間復(fù)雜度，或者可以說覺得比較「美」吧。
問題定義
如果我們把二叉樹看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。寫一個(gè)程序求一棵二叉樹中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。
書上的解法
書中對(duì)這個(gè)問題的分析是很清楚的，我嘗試用自己的方式簡(jiǎn)短覆述。
計(jì)算一個(gè)二叉樹的最大距離有兩個(gè)情況:
情況A: 路徑經(jīng)過左子樹的最深節(jié)點(diǎn)，通過根節(jié)點(diǎn)，再到右子樹的最深節(jié)點(diǎn)。情況B: 路徑不穿過根節(jié)點(diǎn)，而是左子樹或右子樹的最大距離路徑，取其大者。
只需要計(jì)算這兩個(gè)情況的路徑距離，并取其大者，就是該二叉樹的最大距離。
我也想不到更好的分析方法。
但接著，原文的實(shí)現(xiàn)就不如上面的清楚 (源碼可從這里下載):
//?數(shù)據(jù)結(jié)構(gòu)定義
struct?NODE
{
NODE*?pLeft;??????? //?左子樹
NODE*?pRight;?????? //?右子樹
int?nMaxLeft;?????? //?左子樹中的最長(zhǎng)距離
int?nMaxRight;????? //?右子樹中的最長(zhǎng)距離
char?chValue;???? //?該節(jié)點(diǎn)的值
};
int?nMaxLen?=?0;
//?尋找樹中最長(zhǎng)的兩段距離
void?FindMaxLen(NODE*?pRoot)
{
//?遍歷到葉子節(jié)點(diǎn)，返回
if(pRoot?==?NULL)
{
return;
}
//?如果左子樹為空，那么該節(jié)點(diǎn)的左邊最長(zhǎng)距離為0
if(pRoot?->?pLeft?==?NULL)
{
pRoot?->?nMaxLeft?=?0;?
}
//?如果右子樹為空，那么該節(jié)點(diǎn)的右邊最長(zhǎng)距離為0
if(pRoot?->?pRight?==?NULL)
{
pRoot?->?nMaxRight?=?0;
}
//?如果左子樹不為空，遞歸尋找左子樹最長(zhǎng)距離
if(pRoot?->?pLeft?!=?NULL)
{
FindMaxLen(pRoot?->?pLeft);
}
//?如果右子樹不為空，遞歸尋找右子樹最長(zhǎng)距離
if(pRoot?->?pRight?!=?NULL)
{
FindMaxLen(pRoot?->?pRight);
}
//?計(jì)算左子樹最長(zhǎng)節(jié)點(diǎn)距離
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;
}
//?計(jì)算右子樹最長(zhǎng)節(jié)點(diǎn)距離
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;
}
//?更新最長(zhǎng)距離
if(pRoot?->?nMaxLeft?+?pRoot?->?nMaxRight?>?nMaxLen)
{
nMaxLen?=?pRoot?->?nMaxLeft?+?pRoot?->?nMaxRight;
}
}這段代碼有幾個(gè)缺點(diǎn):
算法加入了侵入式(intrusive)的資料nMaxLeft, nMaxRight使用了全局變量 nMaxLen。每次使用要額外初始化。而且就算是不同的獨(dú)立資料，也不能在多個(gè)線程使用這個(gè)函數(shù)邏輯比較復(fù)雜，也有許多 NULL 相關(guān)的條件測(cè)試。我的嘗試
我認(rèn)為這個(gè)問題的核心是，情況A?及 B 需要不同的信息: A 需要子樹的最大深度，B 需要子樹的最大距離。只要函數(shù)能在一個(gè)節(jié)點(diǎn)同時(shí)計(jì)算及傳回這兩個(gè)信息，代碼就可以很簡(jiǎn)單:
#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;
}計(jì)算 result 的代碼很清楚；nMaxDepth 就是左子樹和右子樹的深度加1；nMaxDistance 則取 A 和 B 情況的最大值。
為了減少 NULL 的條件測(cè)試，進(jìn)入函數(shù)時(shí)，如果節(jié)點(diǎn)為 NULL，會(huì)傳回一個(gè) empty 變量。比較奇怪的是 empty.nMaxDepth = -1，目的是讓調(diào)用方 +1 后，把當(dāng)前的不存在的 (NULL) 子樹當(dāng)成最大深度為 0。
除了提高了可讀性，這個(gè)解法的另一個(gè)優(yōu)點(diǎn)是減少了 O(節(jié)點(diǎn)數(shù)目) 大小的侵入式資料，而改為使用 O(樹的最大深度) 大小的?？臻g。這個(gè)設(shè)計(jì)使函數(shù)完全沒有副作用(side effect)。
測(cè)試代碼
以下也提供測(cè)試代碼給讀者參考 (頁數(shù)是根據(jù)第7次印刷，節(jié)點(diǎn)是由上至下、左至右編號(hào)):
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;
} 
下載文檔
