236. Lowest Common Ancestor of a Binary Tree
1. Description
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
2. Example
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3
Input: root = [1,2], p = 1, q = 2
Output: 1
3. Constraints
- The number of nodes in the tree is in the range [2, $10^5$].
- $-10^9$ <= Node.val <= $10^9$
- All Node.val are unique.
- p != q
- p and q will exist in the tree.
4. Solutions
Depth-First Search
n is number of nodes in the root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
TreeNode *common_ancestor = nullptr;
find_common_ancestors(root, p, q, common_ancestor);
return common_ancestor;
}
private:
// Return value:
// 0,1,2 -> number of matched nodes (p/q) found in this subtree
// -1 -> LCA already found; terminate further recursion
int find_common_ancestors(
TreeNode *root,
TreeNode *p,
TreeNode *q,
TreeNode *&common_ancestor) {
if (common_ancestor != nullptr) {
return -1;
}
if (root != nullptr) {
int left_match_count = find_common_ancestors(root->left, p, q, common_ancestor);
if (left_match_count == -1) {
return -1;
}
int right_match_count = find_common_ancestors(root->right, p, q, common_ancestor);
if (right_match_count == -1) {
return -1;
}
int total = left_match_count + right_match_count + int(root == p || root == q);
if (total == 2) {
common_ancestor = root;
return -1;
}
return total;
} else {
return 0;
}
}
};