Longest Tree Path

Given a binary tree root, return the longest path between any two nodes in the tree.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Longest-Tree-Path

Examples

Example 1

Input

• root =

Output

• answer = 6

Explanation

A longest path is [4, 3, 2, 0, 6, 7]

Example 2

Input

• root =

Output

• answer = 5

Explanation

A longest path is [1, 0, 2, 3, 4]

Solution