Binary Trees Depth first: return a value up
349. Diameter of Binary Tree
You are given root, the root node of a binary tree. Return the diameter of the tree.
A path goes from one node to another along the links of the tree, each step from a node to its parent or to one of its children, and it never visits a node twice. The length of a path is the number of steps on it, which is one less than the number of nodes. The diameter is the length of the longest path between any two nodes. That path does not have to pass through the root. An empty tree, and a tree with one node, have diameter 0.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: root = [4, 2, 7, 1, 3, null, 9, null, null, null, null, 8]
5Explanation: The longest path is 1 → 2 → 4 → 7 → 9 → 8. It has 6 nodes, so its length is 5. The path that starts at 3 instead of 1 is just as long.
Example 2
Input: root = [1, 2, null, 3, 4, 5, null, null, 6, 7, null, null, 8]
6Explanation: The longest path is 7 → 5 → 3 → 2 → 4 → 6 → 8, with length 6. It turns at 2 and never reaches the root. The longest path through the root, 1 → 2 → 3 → 5 → 7, has length 4.
Example 3
Input: root = [-5]
0Explanation: A single node has no path to another node, so the diameter is 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.