题目描述（简单难度）

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

二叉搜索树定义如下。

解法一 递归

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

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

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

解法二 迭代

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

  1.     int pVal = p.val;
  2.     int qVal = q.val;
  3.     if (pVal == root.val || qVal == root.val) {
  4.         return root;
  5.     }
  7.     if (pVal > qVal) {
  8.         int temp = pVal;
  9.         pVal = qVal;
  10.         qVal = temp;
  11.     while (true) {
  12.         if (qVal < root.val) {
  14.         } else if (pVal > root.val) {
  15.             root = root.right;
  16.         } else {
  17.             return root;
  18.         }
  19.     }
  20. }

总

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

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^