从头条的面试题到今天的算法课,这个问题已经有好几种解法了。刚好上次讲到了动态规划,这次就顺便整理整理关于树直径的一些求解和思考~

定义

树直径指的是在一棵树中任意两点距离的最大值。需要注意的是,树不一定是二叉树,而直径也不一定经过Root。如下图,树的直径为蓝色的边组成,并没有经过根节点A。

那么如何求树的直径呢?

为简化问题的说明,我们假设该树为二叉树。

递归思路

从某个节点Node的视角,树的直径会有两种情况:经过Node或不经过。所以我们可以从根节点开始递归地解决这个问题,将经过根节点时的候选路径与不经过根节点时的候选路径相比,将长的作为直径。这也是比较容易想到的做法。递推式如下:

1
2
D(T) = 0;
D(T) = max(D(lc), D(rc), H(lc)+H(rc)+2); // lc - left_child, rc - right_child

但是从这个递推式可以发现一个问题,冗余的计算太多了… 跟上次提到的斐波那契差不多,这就回到了“如何优化递归”的问题了。

DP

从递归思路中我们已经找出了递推式了,只需要对递归做个拓扑序列来规划子问题的执行顺序,就能大幅减少多余的运算了。而且递推式中含有H,所以我们首先需要求解所有节点的高度。其实求解节点高度与求解直径问题非常相似,它的递推式为:

1
2
H(T) = 0 if T is a leaf node;
H(T) = 1 + max(H(lc), H(rc));

我们回到刚刚的问题,由于树是一个DAG(有向无环图),所以必定存在某个拓扑序列,而树的拓扑序列也就是其DFS或BFS的结果。由于父节点的“候选直径”的求解依赖于子节点,所以我们可以先求解子节点的“候选直径”。伪代码如下:

1
2
3
4
5
6
7
8
BFS ==> S; // 对树进行BFS操作,然后逐个输出到栈S中,可以获得树节点的逆拓扑序列
while S do
N = S.pop();
if N is leaf_node do
D(T) = 0;
else
D(T) = max(D(lc), D(rc), H(lc)+H(rc)+2);
return D(Root);

另外一种思路

从树的直径定义我们可以看出它是不依赖于树的“既定状态”的。也就是说谁是当前的Root其实不重要,同时“父节点支配子节点”这个关系也不重要。所以我们可以将树的单向边更改为双向边。也就是说,树的每个叶子节点(也就是尽头节点)都可以作为根。由此我们可以看出,如果将树的直径“拉直”,树的形状大概会是这样:

这也就不难理解树的直径有这么一个性质了:距某个点最远的叶子节点一定是树的某一条直径的端点。

所以根据这个性质,我们只要先从某个叶节点O(比如root)开始BFS找出距离它最远的节点P,再从节点P用BFS找出最远的点Q,这样PQ的距离就是直径了。

那么…如何证明这个性质呢?

*** 关键的瞎扯来了 ***

采用反证法,我们假设树T的直径端点为P和Q,任取树中的一点X,不失一般性,我们假设PX.distance > QX.distance,然后存在一个不同于PQ的叶节点R,使得RX.distance > PX.distance。(后面为了简便,用|PQ|代替RQ.distance)

分两种情况讨论:

  • 若X在直径上,则由于RX的距离大于PX也大于QX,所以必有|RX| + |XQ| > |PX| + |XQ| 或 |PX| + |XR| > |PX| + |XQ|,由定义R应该是直径的端点,矛盾
  • 若X不在直径上,可设X到点PQ必须经过的在直径上的第一个点为Y。
    • 若X到达R不需要经过Y,也即它们在一个分支上时,可知有|YR| > |XR| > |XP| ? |XQ|,且有|XP| > |YP|,|XQ| > |YQ|,故YR可替换掉YP或YQ称为直径的一部分,矛盾
    • 若X到达R需要经过Y,也就是它们不在一个分支,同样有|XR| > |XP| ? |XQ|,所以同样减去|XY|,从而有|YR| > |YP| ? |YQ|,故YR可替换掉YP或YQ称为直径的一部分,仍矛盾

因此,距某个点最远的叶子节点一定是树的某一条直径的端点。

溜了溜了。