Diameter of Binary Tree

Given the root of a binary tree, return the **diameter** — the length of the longest path between any two nodes.

The path may or may not pass through the root. The length is measured in **number of edges**.

Input: root = [1,2,3,4,5]

Output: 3

Path [4,2,1,3] or [5,2,1,3], length 3.

Input: root = [1,2]

Output: 1

Single edge between 1 and 2.

Time

O(n)

Space

O(h)

#1 Standard case

Input: [1,2,3,4,5]

Expected: 3

#2 Two nodes

Input: [1,2]

Expected: 1

#3 Single node

Input: [1]

Expected: 0

#4 Left-skewed

Input: [1,2,null,3,null,4]

Expected: 3