Dare2Solve
The problem involves finding the lowest common ancestor (LCA) of two nodes p
and q
in a binary tree. The LCA is defined as the lowest node in the tree that has both p
and q
as descendants.
To find the LCA of nodes p
and q
:
None
or equal to either p
or q
, it is returned as a potential LCA.p
and q
.None
or equals either p
or q
.p
and q
.O(n), where n is the number of nodes in the binary tree. Each node is visited once.
O(n) in the worst case due to recursion stack space, where n is the height of the tree (for a skewed tree).
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) {
return root;
}
TreeNode* resL = lowestCommonAncestor(root->left, p, q);
TreeNode* resR = lowestCommonAncestor(root->right, p, q);
if (resL && resR) {
return root;
} else if (resL) {
return resL;
} else {
return resR;
}
}
};
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# Base case: if root is None or root is either p or q, return root
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# If both left and right subtrees have found nodes, then root is the LCA
if left and right:
return root
return left if left else right
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else {
return right;
}
}
}
function lowestCommonAncestor(root, p, q)
{
if (!root || root === p || root === q) return root;
var resL = lowestCommonAncestor(root.left, p, q);
var resR = lowestCommonAncestor(root.right, p, q);
return (resL && resR) ? root : (resL || resR);
}