二叉樹系列六：求二叉樹葉子結點間的最大距離 [程式設計之美]

題目描述：

  如果把二叉樹看作圖，父子結點間的連線是雙向的，我們姑且定義“距離”為兩個結點之間邊的個數，如下圖所示，相距最遠的兩個結點是A和B，距離為6。寫程式實作二叉樹中相距最遠的兩個結點之間的距離。

思路分析：

  計算一棵二叉樹的最大距離有兩種情況，第一種是路徑經過左子樹的最深結點，通過根節點，再到右子樹的最深結點，那麼距離就是左右子樹的深度和；另一種情況是，路徑不穿過根節點，隻在左子樹或者右子樹，那麼距離就是左子樹和右子樹距離的最大值。

C++代碼實作：

struct TreeNode{
int Lmax;     //左子樹的最長距離
int Rmax;     //右子樹的最長距離
TreeNode* Lchild;
TreeNode* Rchild;
};


//求二叉樹葉子結點的最大距離
int len = ;
int FindMaxLen(TreeNode* root)
{
    if(root == NULL)
        return;
    if(root->Lchild == NULL)
        root->Lmax = ;
    if(root->Rchild == NULL)
        root->Rmax = ;
    if(root->Lchild != NULL)
        FindMaxLen(root->Lchild);
    if(root->Rchild != NULL)
        FindMaxLen(root->Rchild);
    if(root->Lchild != NULL)
    {
        root->Lmax = root->Lchild->Lmax > root->Lchild->Rmax ? (root->Lchild->Lmax + ): (root->Lchild->Rmax + );
    }
    if(root->Rchild != NULL)
    {
        root->Rmax = root->Rchild->Lmax > root->Rchild->Rmax ? (root->Rchild->Lmax + ) : (root->Rchild->Rmax + );
    }
    if((root->Lmax + root->Rmax) > len)
    {
        len = root->Lmax + root->Rmax;
    }
    return Len;
}