求解二叉树结点间的最大距离

例如这样一棵二叉树：

什么叫做二叉树结点间的最大距离呢？例如从结点a出发，可以向上走或向下走，但沿途的结点只能经过一次，到达结点b时路径上经过的结点个数叫做a到b的距离，因此，二叉树任意两个结点间都有距离，那么也就存在一个最大距离。

上图二叉树中B到C的距离就是3.最大距离容易得出是6，为G到F的距离。

所谓最大距离，可以分为三种情况，最大距离就在根结点的左子树上，或者右子树上，这两种情况下，根结点都是不参与进去的。所谓不参与进去就是计算最大距离路径上结点时不把根结点也算进去。那么第三种情况就包含了根结点，也就是说求解最大距离时的路径需要经过根结点，也就是上图二叉树中的这种情况。因此，为了实现程序，我们可以用递归的方法：

 1 public class MaxDistance {
 2     private static class Node {
 3         public char value;
 4         public Node left;
 5         public Node right;
 6 
 7         public Node(char value, Node left, Node right) {
 8             this.left = left;
 9             this.right = right;
10             this.value = value;
11         }
12     }
13 
14     public static class Info {
15         public int maxDistance;
16         public int height;
17 
18         public Info(int dis, int h) {
19             maxDistance = dis;
20             height = h;
21         }
22     }
23 
24     private static Info process(Node node) {
25         if (node == null) {
26             return new Info(0, 0);
27         }
28         Info leftInfo = process(node.left);
29         Info rightInfo = process(node.right);
30         int d1 = leftInfo.maxDistance;
31         int d2 = rightInfo.maxDistance;
32         int d3 = leftInfo.height + 1 + rightInfo.height;
33         int maxDistance = Math.max(d1, Math.max(d2, d3));
34         int height = Math.max(leftInfo.height, rightInfo.height) + 1;
35         return new Info(maxDistance, height);
36     }
37 
38     public static int getMaxDistance(Node head) {
39         return process(head).maxDistance;
40     }
41 
42     public static void main(String[] args) {
43         Node nodeG = new Node('B', null, null);
44         Node nodeD = new Node('B', null, null);
45         Node nodeE = new Node('B', nodeG, null);
46         Node nodeF = new Node('B', null, null);
47         Node nodeB = new Node('B', nodeD, nodeE);
48         Node nodeC = new Node('B', null, nodeF);
49         Node nodeA = new Node('A', nodeB, nodeC);
50         int distance = getMaxDistance(nodeA);
51         System.out.println(distance);
52     }
53 }

这其中的核心方法是这个：

private static Info process(Node node) {
        if (node == null) {
            return new Info(0, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int d1 = leftInfo.maxDistance;
        int d2 = rightInfo.maxDistance;
        int d3 = leftInfo.height + 1 + rightInfo.height;
        int maxDistance = Math.max(d1, Math.max(d2, d3));
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new Info(maxDistance, height);
    }

我需要取得某一个结点的左子树和右子树的情况，当然对应于第三种情况，两边树高再加上结点本身就是距离，这三个数比较一下大小，很容易就能算出最大距离，同时，还要记录算上当前结点的树高，全部计算完毕后，把这个对象返回出去即可。

运行也无问题：

求解二叉树结点间的最大距离

推荐阅读