864. Find Distance Between Two Nodes

Given the root of a binary tree and two node values p and q (both present), return the number of edges on the shortest path between them. This equals depth(p) plus depth(q) minus twice the depth of their lowest common ancestor. The input gives a level-order tree array and the two values separated by ' | '.

Input: A level-order tree array and two values, separated by ' | '.

Output: Integer — the distance in edges.

Examples

Input: [3,5,1,6,2,0,8] | 5 1
Output: 2
Explanation: 5 and 1 are both children of 3.

Input: [3,5,1,6,2,0,8] | 6 8
Output: 4
Explanation: Path 6-5-3-1-8 has 4 edges.

Input: [1,2,3] | 2 3
Output: 2
Explanation: Two edges via the root.

Constraints

• 2<=nodes<=10^4
• node values are unique
• p and q exist

Asked by