Diameter of Binary Tree

Easy·Tagstreedfsrecursion

Problem Statement

Given the `root` of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

Examples

Example 1

Input

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

Tree

Output

"3"

Why

3 is the length of the path [4, 2, 1, 3] or [5, 2, 1, 3]. There are 3 edges between the start and end nodes.

Example 2

Input

root: [1, 2]

Tree

Output

"1"

Why

The longest path is [1, 2] which has 1 edge.

Constraints

•The number of nodes in the tree is in the range [1, 10^4].
•-100 <= Node.val <= 100

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

The diameter of a tree at any given node is simply the maximum depth of its left subtree PLUS the maximum depth of its right subtree.

Hint 2

However, the longest path might not go through the root node! It could exist entirely within a deeply nested subtree.

Hint 3

Write a recursive DFS function that calculates the maximum depth (height) of a node. As a side-effect during this recursion, keep track of the maximum diameter you have seen so far in a global or reference variable.

Hint 4

For any node, its height is `1 + max(left_height, right_height)`. But you should update your global diameter tracker using `left_height + right_height`.