每日一题：二叉树节点的最大距离问题

1：不经过x，则 ①：左孩子上有最大距离 ②：右孩子上有最大距离
2：经过x，则最大距离为：左树高 + 1 + 右树高

代码：

public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int value) {
        this.value = value;
    }
}

public static int maxDistance (Node head) {
    return process(head).maxDistance;    
}

public static class Info {
    public int maxDistance;
    public int height;
    public Info (int dis, int h) {
        this.maxDistance = dis;
        this.height = h;
    }
}

//返回以x为头节点的树的最大距离和最大高度
public static Info process(Node x) {
    if (x == null) {
        return new Info(0,0);
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int p1 = leftInfo.maxDistance;
    int p2 = rightInfo.maxDistance;
    int p3 = leftInfo.height + 1 + rightInfo.height;
    int maxDistance = Math.max(p3, Math.max(p1, p2));
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    return new Info(maxDistance, height);
}
//测试
public static void String(String[] args) {
    Node head1 = new Node(1);
    head1.left = new Node(2);
    head1.right = new Node(3);
    head1.left.left = new Node(4);
    head1.left.right = new Node(5);
    head1.right.left = new Node(6);
    head1.right.right = new Node(7);
    head1.left.left.left = new Node(8);
    head1.right.left.right = new Node(9);
    //返回以head1为头节点的树的最大距离
    System.out.println(maxDistance(head1));
}