题目描述（简单难度）

从二叉搜索树中，找出两个节点的最近的共同祖先。

二叉搜索树定义如下。

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

解法一 递归

由于是二叉搜索树，所以找最近的共同祖先比较容易，总共就三种情况。

• 如果给定的两个节点的值都小于根节点的值，那么最近的共同祖先一定在左子树
• 如果给定的两个节点的值都大于根节点的值，那么最近的共同祖先一定在右子树
• 如果一个大于等于、一个小于等于根节点的值，那么当前根节点就是最近的共同祖先了

至于前两种情况用递归继续去解决即可。

代码的话，我们可以通过交换使得 p.val <= q.val ，这样就可以简化后边 if 语句的判断。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 保持 p.val <= q.val if (p.val > q.val) { return lowestCommonAncestor(root, q, p); } //如果有一个是根节点就可以提前结束, 当然这个 if 不要也可以 if (p.val == root.val || q.val == root.val) { return root; } if (q.val < root.val) { return lowestCommonAncestor(root.left, p, q); } else if (p.val > root.val) { return lowestCommonAncestor(root.right, p, q); } else { return root; } } 

解法二 迭代

上边的递归比较简单，可以直接改写成循环的形式。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { int pVal = p.val; int qVal = q.val; if (pVal == root.val || qVal == root.val) { return root; } // 保持 p.val <= q.val if (pVal > qVal) { int temp = pVal; pVal = qVal; qVal = temp; } while (true) { if (qVal < root.val) { root = root.left; } else if (pVal > root.val) { root = root.right; } else { return root; } } } 

总

只要知道二叉搜索树的定义，这个题就很好解了。当然之前的题目都是用的二叉搜索树的另一个性质，「中序遍历输出的是一个升序数组」，比如刚做完的 230 题。

对于二叉树的题，开始可以用递归的思想去思考会比较简单。