Share the joy
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