Find the Lowest Node Above Both Chosen Nodes
Implement lowestSharedAncestor
You are given the root of a binary tree in which all node values are distinct, and two values p and q that are both present in the tree. Return the value of the lowest node that has both the node holding p and the node holding q somewhere in its subtree. A node is considered to be part of its own subtree, so if one of the two chosen nodes lies below the other, the upper one is the answer.
You can compare the root paths of the two nodes, or use a single recursive pass in which each subtree reports whether it contains a target.
Example 1:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], p = 6, q = 13
Output: 8
Example 2:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], p = 6, q = 4
Output: 4
Example 3:
Input: root = [15,8,22,4,11,19,30,2,6,9,13], p = 2, q = 30
Output: 15
+ 13 hidden test cases run on Submit.
Constraints:
- ●
2 ≤ number of nodes ≤ 100, and every node value is distinct, 1 ≤ node.val ≤ 1000 - ●
p and q are values that both exist in the tree (they may be equal to each other) - ●
The tree is given as its root node; each node has a val, a left child and a right child - ●
Return the value of the lowest node that has both the p-node and the q-node in its subtree. A node counts as being in its own subtree, so if one chosen node is above the other, the answer is the upper one
root =
p =
q =