Diameter of a binary tree
You get the root of a binary tree with at least one node. A path is a chain of nodes where each node is joined to the next by a parent and child link, and no node appears twice. The length of a path is its number of links (edges), one fewer than its number of nodes.
Return the length of the longest path in the tree, called its diameter. A path may go up from one node to some higher node and then down to another, and that higher node does not have to be the root.
Examples write a tree level by level, left to right, with None where a child is missing.
root = [1, 2, 3, None, 4, None, 5]Output4The path 4, 2, 1, 3, 5 has five nodes and four edges.
root = [1, 2, None, 3, 4, 5, None, None, 6]Output4The path 5, 3, 2, 4, 6 stays below the root. A path through the root has at most 3 edges, because the root has only one child.
root = [7]Output0One node, so no edges.
1 ≤ number of nodes ≤ 2 × 105
The tree is at most 900 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
-100 ≤ val ≤ 100
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.