二叉树的最大距离

问题定义

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

对于任意一个节点，以该节点为根，假设这个根有k个孩子节点，那么距离最远的两个节点U与V之间的路径与这个根节点的关系有两种。

1).若路径经过Root，则U和V属于不同子树的，且它们都是该子树中到根节点最远的节点，否则跟它们的距离最远相矛盾

2).如果路径不经过Root，那么它们一定属于根的k个子树之一，并且它们也是该子树中相距最远的两个顶点

因此，问题就可以转化为在字数上的解，从而能够利用动态规划来解决。

设第K棵子树中相距最远的两个节点：Uk和Vk，其距离定义为d(Uk,Vk)，那么节点Uk或Vk即为子树K到根节点Rk距离最长的节点。不失一般性，我们设Uk为子树K中道根节点Rk距离最长的节点，其到根节点的距离定义为d(Uk,R)。取d(Ui,R)(1<=i<=k)中最大的两个值max1和max2，那么经过根节点R的最长路径为max1+max2+2，所以树R中相距最远的两个点的距离为：max{d(U1,V1),…, d(Uk,Vk),max1+max2+2}。

情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。

只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。

 1 // 数据结构定义 
 2 struct NODE
 3 {
 4     NODE* pLeft; // 左子树 
 5     NODE* pRight; // 右子树 
 6     int nMaxLeft; // 左子树中的最长距离 
 7     int nMaxRight; // 右子树中的最长距离 
 8     char chValue; // 该节点的值 
 9 };
10 int nMaxLen = 0;
11 // 寻找树中最长的两段距离 
12 void FindMaxLen(NODE* pRoot)
13 {
14     // 遍历到叶子节点，返回 
15     if(pRoot == NULL)
16     {
17         return;
18     }
19     // 如果左子树为空，那么该节点的左边最长距离为0 
20     if(pRoot -> pLeft == NULL)
21     {
22         pRoot -> nMaxLeft = 0;
23     }
24     // 如果右子树为空，那么该节点的右边最长距离为0 
25     if(pRoot -> pRight == NULL)
26     {
27         pRoot -> nMaxRight = 0;
28     }
29      // 如果左子树不为空，递归寻找左子树最长距离 
30     if(pRoot -> pLeft != NULL)
31     {
32         FindMaxLen(pRoot -> pLeft);
33     }
34     // 如果右子树不为空，递归寻找右子树最长距离 
35     if(pRoot -> pRight != NULL)
36     {
37         FindMaxLen(pRoot -> pRight);
38     }
39     // 计算左子树最长节点距离 
40     if(pRoot -> pLeft != NULL)
41     {
42         int nTempMax = 0;
43         if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
44         {
45             nTempMax = pRoot -> pLeft -> nMaxLeft;
46         }
47         else
48         {
49             nTempMax = pRoot -> pLeft -> nMaxRight;
50         }
51         pRoot -> nMaxLeft = nTempMax + 1;
52     }
53      // 计算右子树最长节点距离 
54     if(pRoot -> pRight != NULL)
55     {
56         int nTempMax = 0;
57         if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
58         {
59             nTempMax = pRoot -> pRight -> nMaxLeft;
60         }
61         else
62         {
63             nTempMax = pRoot -> pRight -> nMaxRight;
64         }
65         pRoot -> nMaxRight = nTempMax + 1;
66     }
67     // 更新最长距离 
68     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
69     {
70         nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
71     }
72 }