333. Diameter of a Tree
The diameter is the number of nodes on the longest path between any two nodes. The path does not have to pass through the root.
4
/ \
2 6 diameter is 5, for example 1 2 4 6 7
/ \ / \
1 3 5 7
At every node there is a candidate path that goes down into the left subtree,
through this node, and down into the right: its length is
leftHeight + rightHeight + 1. The diameter is the largest such candidate over
all nodes.
The efficient version computes each height once and updates the best answer on the way back up. Computing the height separately at every node re-walks the same subtrees over and over and turns a linear solution into a quadratic one.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print one integer, the diameter measured in nodes.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.