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^(h-1). h is max tree depth.
Add them up, the result is (n+1) * h - (1 + 2 + 4 ... + 2^(h-1)). In worst case, the latter part is n (all nodes in the tree), so time complexity is O(n*logn).
This solution is wrong because it returns the max depth of the left, and the right, respective from the root only.
What about if our solution lies elsewhere?
/ \ / \
g h i j
If we only did the max of the left + right, we'd get 4 + 1, so 5, but it's pretty clear the bigger route is down on the left side, through 'c'.
Basically at each node we have 2 actions. We need to look at both branches combined to see how they compare to the overall max thus far, and we need to contribute a left or right side, whichever is more, so the other nodes higher up in the tree can attempt to do the same calculation of the sum of their branches against the current max.
Another thing to note is we cannot return the value of both of a nodes branches (left + right), because then it might get calculated into another node's calculation of both of it's branches. We'd end up with forked routes which are invalid. That is the reasoning for most of these solutions hoisting a max value our of their functions.