236. Lowest Common Ancestor of a Binary Tree#

 1private TreeNode ans = null;
 2
 3private boolean lca(TreeNode currentNode, TreeNode p, TreeNode q) {
 4  if (currentNode == null) return false;
 5
 6  int curr = (currentNode == p || currentNode == q) ? 1 : 0;
 7  int left = lca(currentNode.left, p, q) ? 1 : 0;
 8  int right = lca(currentNode.right, p, q) ? 1 : 0;
 9
10  if ((left + curr + right) > 1) {
11    ans = currentNode;
12  }
13
14  return (left + curr + right) > 0;
15}
16
17public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
18  lca(root, p, q);
19  return ans;
20}

 1public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 2  if (root == null || root == p || root == q) {
 3    return root;
 4  }
 5
 6  TreeNode left = lowestCommonAncestor(root.left, p, q);
 7  TreeNode right = lowestCommonAncestor(root.right, p, q);
 8
 9  if (left != null && right != null) {
10    return root;
11  }
12
13  return left == null ? right : left;
14}