程式設計之美: 求二叉樹中節點的最大距離》的好解法

轉自 ：http://aclay.blog.163.com/blog/static/208468235201272392954636/

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

問題定義

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

書上的解法

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

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

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

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

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

struct node { //
    node* left;
    node* right;
};
struct Result { // 記錄的最大深度 和 最大距離
    int MaxDis;
    int MaxDep;
};

Result get_dis(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 = get_dis(root->left);
    Result rhs = get_dis(root->right);
    Result res;
    res.MaxDep = max(lhs.MaxDep, rhs.MaxDep) + 1;
    res.MaxDis = max(max(lhs.MaxDis, rhs.MaxDis), lhs.MaxDep + rhs.MaxDep + 2);
    return res;
}
void link(node* arr, int par, int left, int right) {
    if(left != -1) {
        arr[par].left = &arr[left];
    }
    if(right != -1) {
        arr[par].right = &arr[left];
    }
}
int main() {
    node arr[105] = {0};
    link(arr, 0, 1, 2);
    link(arr, 1, 3, 4);
    link(arr, 2, 5, 6);
    link(arr, 3, 7, -1);
    link(arr, 5, -1, 8);
    cout << get_dis(&arr[0]).MaxDis << endl;
    return 0;
}


  

        

 評論這張

轉發至微網誌