雁過(guò)無(wú)痕

《編程之美》讀書(shū)筆記12： 3.8 求二叉樹(shù)中節(jié)點(diǎn)的最大距離

問(wèn)題：

如果我們把二叉樹(shù)看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線(xiàn)看成是雙向的，我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。寫(xiě)一個(gè)程序求一棵二叉樹(shù)中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。

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

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

static int tree_height(Node* root, int& max_distance)
{
  //每碰到一個(gè)子節(jié)點(diǎn)，高度自增1，可以設(shè)空節(jié)點(diǎn)高度為-1，
  //避免計(jì)算高度時(shí)對(duì)空節(jié)點(diǎn)的判斷。
  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;
}