题解 | #二叉搜索树的最近公共祖先#

基于BST的特点，遍历就行

public int lowestCommonAncestor2(TreeNode root, int p, int q) {
  while (root != null) {
	if (root.val > p && root.val > q) { // p,q 都在 root 的左子树中
	  root = root.left;
	} else if (root.val < p && root.val < q) { // p,q 都在 root 的右子树中
	  root = root.right;
	} else {
	  break;
	}
  }
  return root == null ? -1 : root.val;
}

平均时间复杂度 O(lgn)，空间复杂度 O(1)

下面是递归实现

public int lowestCommonAncestor(TreeNode root, int p, int q) {
  // 递归终止条件
  if (root == null) return -1;
  // 递归过程
  if (root.val > p && root.val > q) { // p,q 都在 root 的左子树中
	return lowestCommonAncestor(root.left, p, q);
  }
  if (root.val < p && root.val < q) { // p,q 都在 root 的右子树中
	return lowestCommonAncestor(root.right, p, q);
  }
  // p,q 一个在 root 的左子树中，一个在 root 的右子树中
  return root.val;
}

平均时间复杂度 O(lgn)，空间复杂度 O(树的高度)