如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，我們姑且定義“距
離”為兩個節點之間邊的個數。
寫一個程序求一棵二叉樹中相距最遠的兩個節點之間的距離。
如圖 3-11 所示，粗箭頭的邊表示最長距離：
圖 3-11
樹中相距最遠的兩個節點 A，B
寫書評，贏取《編程之美——微軟技術面試心得》
www.ieee.org.cn/BCZM.asp
分析與解法
我們先畫幾個不同形狀的二叉樹，（如圖 3-12 所示），看看能否得到一些啟示。
圖 3-12
幾個例子
從例子中可以看出，相距最遠的兩個節點，一定是兩個葉子節點，或者是一個葉子節點
到它的根節點。（為什么？）
【解法一】
根據相距最遠的兩個節點一定是葉子節點這個規律，我們可以進一步討論。
對于任意一個節點，以該節點為根，假設這個根有 K 個孩子節點，那么相距最遠的兩
個節點 U 和 V 之間的路徑與這個根節點的關系有兩種情況：
1. 若路徑經過根Root，則U和V是屬于不同子樹的，且它們都是該子樹中到根節點最遠
的節點，否則跟它們的距離最遠相矛盾。這種情況如圖3-13所示：
圖 3-13
相距最遠的節點在左右最長的子樹中
寫書評，贏取《編程之美——微軟技術面試心得》
www.ieee.org.cn/BCZM.asp
2. 如果路徑不經過Root，那么它們一定屬于根的K個子樹之一。并且它們也是該子樹中
相距最遠的兩個頂點。如圖3-14中的節點A：
圖 3-14
相距最遠的節點在某個子樹下
因此，問題就可以轉化為在子樹上的解，從而能夠利用動態規劃來解決。
設第 K 棵子樹中相距最遠的兩個節點：Uk 和 Vk，其距離定義為 d（Uk, Vk），那么節點
Uk 或 Vk 即為子樹 K 到根節點 Rk 距離最長的節點。不失一般性，我們設 Uk 為子樹 K 中到根
節點 Rk 距離最長的節點，其到根節點的距離定義為 d（Uk, R）。取 d（Ui, R）（1≤i≤k）中
最大的兩個值 max1 和 max2，那么經過根節點 R 的最長路徑為 max1+max2+2，所以樹 R 中
相距最遠的兩個點的距離為：max{d（U1, V1）, …, d（Uk, Vk），max1+max2+2}。
采用深度優先搜索如圖 3-15，只需要遍歷所有的節點一次，時間復雜度為 O（|E|）= O
（|V|-1），其中 V 為點的集合，E 為邊的集合。
圖 3-15
深度遍歷示意圖
示例代碼如下，我們使用二叉樹來實現該算法。
代碼清單 3-11
// 數據結構定義
寫書評，贏取《編程之美——微軟技術面試心得》
www.ieee.org.cn/BCZM.asp
struct NODE
{
NODE* pLeft;
NODE* pRight;
int nMaxLeft;
int nMaxRight;
char chValue;
};
int nMaxLen = 0;
// 尋找樹中最長的兩段距離
void FindMaxLen(NODE* pRoot)
{
// 遍歷到葉子節點，返回
if(pRoot == NULL)
{
return;
}
// 如果左子樹為空，那么該節點的左邊最長距離為0
if(pRoot -> pLeft == NULL)
{
pRoot -> nMaxLeft = 0;
}
// 如果右子樹為空，那么該節點的右邊最長距離為0
if(pRoot -> pRight == NULL)
{
pRoot -> nMaxRight = 0;
}
// 如果左子樹不為空，遞歸尋找左子樹最長距離
if(pRoot -> pLeft != NULL)
{
FindMaxLen(pRoot -> pLeft);
}
// 如果右子樹不為空，遞歸尋找右子樹最長距離
if(pRoot -> pRight != NULL)
{
FindMaxLen(pRoot -> pRight);
}
// 計算左子樹最長節點距離
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;
}
// 計算右子樹最長節點距離
if(pRoot -> pRight != NULL)
//
//
//
//
//
左孩子
右孩子
左子樹中的最長距離
右子樹中的最長距離
該節點的值
寫書評，贏取《編程之美——微軟技術面試心得》
www.ieee.org.cn/BCZM.asp
{
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;
}
}
擴展問題
在代碼中，我們使用了遞歸的辦法來完成問題的求解。那么是否有非遞歸的算法來解決
這個問題呢？
總結
對于遞歸問題的分析，筆者有一些小小的體會：
1. 先弄清楚遞歸的順序。在遞歸的實現中，往往需要假設后續的調用已經完成，在此
基礎之上，才實現遞歸的邏輯。在該題中，我們就是假設已經把后面的長度計算出
來了，然后繼續考慮后面的邏輯；
2. 分析清楚遞歸體的邏輯，然后寫出來。比如在上面的問題中，遞歸體的邏輯就是如
何計算兩邊最長的距離；
3. 考慮清楚遞歸退出的邊界條件。也就說，哪些地方應該寫return。
注意到以上 3 點，在面對遞歸問題的時候，我們將總是有章可循。
-----------------------------------------------------------------------------------
《編程之美》讀書筆記：第3.8節“求二叉樹中節點的最大距離”擴展問題 收藏
感謝azuryy為大家分享《編程之美》第3.8節擴展問題的答案：用非遞歸的算法求一顆二叉樹中相距最遠的兩個節點之間的距離。（原博客地址：http://hi.baidu.com/azuryy/blog/item/30ad10ea192424d5d439c96d.html）
#include <stack>
#include <algorithm>
using namespace std;
struct Node
{
bool _visited;
Node* left;
Node* right;
int maxLeft;
int maxRight;
Node()
{
_visited = false;
maxLeft = 0;
maxRight = 0;
left = NULL;
right = NULL;
}
};
int maxLen = 0;
stack<Node*> nodeStack;
void findMaxLen( Node* root )
{
Node* node;
if ( root == NULL )
{
return ;
}
nodeStack.push( root );
while( !nodeStack.empty())
{
node = nodeStack.top();
if ( node->left == NULL && node->right == NULL )
{
nodeStack.pop();
node->_visited = true;
continue;
}
if ( node->left )
{
if ( !node->left->_visited )
{
nodeStack.push( node->left ) ;
}
else
{
node->maxLeft = max( node->left->maxLeft,node->left->maxRight ) + 1;
}
}
if ( ( !node->left || node->left->_visited ) && node->right )
{
if ( !node->right->_visited )
{
nodeStack.push( node->right ) ;
}
else
{
node->maxRight = max( node->right->maxLeft,node->right->maxRight ) + 1;
}
}
if (( !node->left || node->left->_visited ) && ( !node->right || node->right->_visited ))
{
maxLen = max( maxLen, node->maxLeft + node->maxRight );
node->_visited = true;
nodeStack.pop();
}
}
}
Immediate test case 1：
int main()
{
Node *tmp ;
Node* root = new Node();
tmp = new Node();
root->left = tmp ;
tmp = new Node();
root->right = tmp;
tmp = new Node();
root->right->right = tmp;
tmp = new Node();
root->right->right->right = tmp;
tmp = new Node();
root->right->right->right->left = tmp;
findMaxLen( root );
cout << maxLen << endl;
return 0;
}
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/bvbook/archive/2008/07/25/2710209.aspx