863. Find Lowest Common Ancestor (LCA)

Given the root of a binary tree and two distinct node values p and q (both present in the tree), return the value of their lowest common ancestor — the deepest node that has both p and q as descendants (a node may be a descendant of itself). 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 LCA node value.

Examples

Input: [3,5,1,6,2,0,8] | 5 1
Output: 3
Explanation: 3 is the lowest ancestor of 5 and 1.

Input: [3,5,1,6,2,0,8] | 6 2
Output: 5
Explanation: 5 is the lowest common ancestor.

Input: [1,2,3] | 2 3
Output: 1
Explanation: Root is the LCA.

Constraints

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

Asked by