二叉树的直径就是任意两点之间的最大距离。图中直径为[4,2,1,3]。
可以看到，图中的树直径为4到3之间的距离，而经过1点的距离才是最长的。
可以将这条最长的路径分为两部分，即[1,2,4] + [1,3]，因此可以将这个问题转化为：求左右子树最大深度之和。
//遍历所有节点，返回 节点的左右子树最大深度之和 与子节点的左右子树最大深度之和 的最大值
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int maxDepth = depth(root.left) + depth(root.right);
return max(maxDepth, diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
}
//求深度
public int depth(TreeNode root) {
if (root == null) return 0;
return 1 + max(depth(root.left), depth(root.right));
}
public int max(int p, int q) {
return p > q ? p : q;
}
public int max(int o, int p, int q) {
return max(max(o, p), q);
}
