public class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
int dia = depth(root.left) + depth(root.right);
int ldia = diameterOfBinaryTree(root.left);
int rdia = diameterOfBinaryTree(root.right);
return Math.max(dia,Math.max(ldia,rdia));
}
public int depth(TreeNode root){
if(root == null){
return 0;
}
return 1+Math.max(depth(root.left), depth(root.right));
}
}
Java easy to understand solution


this solution is intuitive but the performance is not good because of the overlapping subproblems when calculate depth.
diameterOfBinaryTree is called on every node. In each call, it traverses all descendants of that node to get the depth.
 for root node, it is
n => n + 1  2^0
 for all nodes on 2nd level, it is
2 * (n  1) / 2 => n  1 => n + 1  2^1
 for all nodes on 3rd level, it is
4 * (n  3) / 4 => n  3 => n + 1  2^2
 for all nodes on 4th level, it is
8 * (n  7) / 8 => n  7 => n + 1  2^3
...  for all nodes on last level, it is
n + 1  2^(h1)
.h
is max tree depth.
Add them up, the result is
(n+1) * h  (1 + 2 + 4 ... + 2^(h1))
. In worst case, the latter part is n (all nodes in the tree), so time complexity isO(n*logn)
.
 for root node, it is