雁過無痕

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

問題：

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

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

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;
}