【Daily Interview】- 18 二叉树的最近公共祖先

题目

!! 题目来源：二叉树的最近公共祖先 - 力扣

分析

首先对于树的问题，首先自然是想到递归，设当前被遍历到的节点为 current，那么对于 current 和 p，q 的关系，无非以下几种：

• p，q 皆在 current 左边
• p，q 皆在 current 右边
• p，q 分别在 current 两边

而对前两种情况，很简单，朝着相反的方向找即可，但对于第三种情况则不好确定应该怎么查找，譬如下图：

对于这种情况，我们可以看到，p，q 是分别在 root 的左右两棵子树上的，那么这里我们可以通过 left 和 right 来遍历两棵子树：如若没找到 p 或者 q，则舍弃掉这棵子树。这样就可以不断缩小查找的范围，直至最后找到两个节点的最近公共祖先。

具体代码如下：

var lowestCommonAncestor = function (root, p, q) {
  if (root === null || root === p || root === q) return root;
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (left === null) return right;
  if (right === null) return left;
  return root;
};

结果如下：

拓展

!! 题目来源：二叉搜索树的最近公共祖先 - 力扣

这道题相对上面其实更加简单，首先我们要知道什么是二叉搜索树：在二叉树的基础上，左 < root < 右，则被称为二叉搜索树。

!! ?tip：需要注意的是，左子树的节点要全都小于 root，右子树同样

如下图所示：

而上面的结构有一个特点：当进行中序遍历的时候，所得到的结果一定是一个依次递增的序列。

大致了解了二叉搜索树的特征之后，对于公共祖先，显然有了更加简便的查找方式：

• 当 p，q 皆大于 current 的时候，向右查找
• 当 p，q 皆小于 current 的时候，向左查找
• 否则说明找到了二者的最近公共祖先

具体代码如下：

var lowestCommonAncestor = function (root, p, q) {
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestor(root.right, p, q);
  } else if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestor(root.left, p, q);
  } else {
    return root;
  }
};

值得一提的是，由于不需要记录状态，所以这个问题即使使用迭代也不需要借助栈或者队列之类的数据结构：

var lowestCommonAncestor = function (root, p, q) {
    while (root) {
      if (p.val > root.val && q.val > root.val) {
        root = root.right;
      } else if (p.val < root.val && q.val < root.val) {
        root = root.left;
      } else {
        return root;
      }
    }
};

结果如下：