雁過無痕

《編程之美》讀書筆記12： 3.8 求二叉樹中節點的最大距離

問題：

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

實際上就是求樹的直徑。若采用“動態規劃方法”思想，會將該問題分解成“具有最大距離兩點間的路徑是否經過根節點”兩個子問題，然后再對這兩個子問題求解判斷。實際上，不必這么麻煩。距離最遠的兩點必然在以某個節點A為根的子樹上，它們間的路徑必然經過該子樹的根節點A。因而，以任意一個節點B為根的子樹，計算出經過該子樹根節點B的最大距離，則所有最大距離的最大值就是所要求的二叉樹的最大距離，即“樹的直徑”。而經過樹的根節點的最大距離為：左子樹的高度+右子樹的高度+2（假設空節點的高度為-1），因而，原問題等同于“計算每個節點的左子樹和右子樹的高度和，取最大值”。

struct Node {
  Node *left;
  Node *right;
  int data;
};

static int tree_height(Node* root, int& max_distance)
{
  //每碰到一個子節點，高度自增1，可以設空節點高度為-1，
  //避免計算高度時對空節點的判斷。
  if (root == NULL) return -1;
  int left_height = tree_height(root->left, max_distance) + 1;
  int right_height = tree_height(root->right, max_distance) + 1;
  int distance = left_height + right_height;
  if (max_distance < distance) max_distance = distance;
  return  left_height > right_height ? left_height : right_height;
}

int tree_diameter(Node* root)
{
  int max_distance = 0;
  tree_height(root, max_distance);
  return max_distance;
}