Binary Trees Depth first: return a value up
352. Lowest Common Ancestor of a Binary Tree
You are given root, the root node of a binary tree, and two different nodes of the tree, p and q.
Return their lowest common ancestor.
A node is an ancestor of another node when the other node is in its subtree: below it, or the node
itself. So every node is an ancestor of itself. The lowest common ancestor of p and q is the deepest
node that is an ancestor of both.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out. The values in the tree are distinct, so the examples name
p, q and the node you return by their values.
Example 1
Input: root = [6, -2, 9, 4, 0, null, 3, null, null, 8, -7]
p = 4
q = -7
-2Explanation: 4 is the left child of −2, and −7 is below 0, the right child of −2. So −2 has both nodes in its subtree, and no deeper node does. The root 6 is a common ancestor too, but it is higher up.
Example 2
Input: root = [5, 1, 8, null, 7, null, null, 2, 3]
p = 1
q = 3
1Explanation: 3 is below 1, on the path 1 → 7 → 3. Since 1 is an ancestor of itself, 1 is the lowest common ancestor.
Example 3
Input: root = [-1000000000, 1000000000]
p = 1000000000
q = -1000000000
-1000000000Explanation: The tree has two nodes. q is the root and p is its child, so the root is the answer.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
2 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
- All the values in the tree are distinct.
p ≠ q, and both are nodes of the tree.
Clarifying questions
What you would ask an interviewer before writing any code.