Lowest Common Ancestor of a Binary Tree
You are given the root of a binary tree whose node values are all distinct, and two different values p and q that both appear in the tree.
Return the value of their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as part of its own subtree, so if the node holding p is an ancestor of the node holding q, the answer is p.
The tree is a general binary tree, not necessarily a binary search tree. Return a number (the ancestor's val), not the node itself.
Constraints
- The tree has between
2and10^4nodes. -10^9 <= Node.val <= 10^9, and all values are distinct.p !== q, and both values exist in the tree.
Examples
Example 1
Input: root = [10,4,7,1,9,3,12,null,null,6,2,null,11], p = 6, q = 2 Output: 9
6 and 2 are both children of 9, so 9 is the deepest node with both below it.
Example 2
Input: root = [10,4,7,1,9,3,12,null,null,6,2,null,11], p = 4, q = 2 Output: 4
2 is in the subtree of 4, and a node counts as its own ancestor, so the answer is 4.
Example 3
Input: root = [10,4,7,1,9,3,12,null,null,6,2,null,11], p = 1, q = 11 Output: 10
1 is on the left of the root and 11 on the right, so their paths only meet at the root, 10.
JavaScript you'll use: Recursion, the call stack and memoization Linked list and tree nodes
/**
* Tree nodes are provided (you don't need to define them):
* class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
*/
/**
* @param {TreeNode} root
* @param {number} p
* @param {number} q
* @return {number}
*/
function lowestCommonAncestor(root, p, q) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.