I wrote finding lca long time ago. Today, I learned this more concise code for finding LCA in Binary Tree.
The idea is that if there is no p or q in bottom, return null. Or return p, q or root.
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == p || root == q || root == null) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
return right;
}
Check my code on github: link
Below is the finding LCA in BST.
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
int max = Math.max(p.val, q.val);
int min = Math.min(p.val, q.val);
if (root.val >= min && root.val <= max) {
return root;
}
return root.val > max ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);
}
Check my code on github: link