给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {


    private Info solve(TreeNode root) {
        if (root == null) {
            return new Info(0, 0);
        }
        Info left = solve(root.left);
        Info right = solve(root.right);

        int res = Math.max(Math.max(left.res, right.res), left.nodes + right.nodes);
        int nodes = Math.max(left.nodes, right.nodes) + 1;

        return new Info(res, nodes);
    }

    public int diameterOfBinaryTree(TreeNode root) {
        return solve(root).res;
    }
}

class Info {
    int res;
    int nodes;

    public Info(int res, int nodes) {
        this.res = res;
        this.nodes = nodes;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}