题目描述（简单难度）

235. Lowest Common Ancestor of a Binary Search Tree - 图1

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

二叉搜索树定义如下。

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

解法一 递归

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

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

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

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

  1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.     // 保持 p.val <= q.val
  4.     if (p.val > q.val) {
  5.         return lowestCommonAncestor(root, q, p);
  6.     }
  7.     //如果有一个是根节点就可以提前结束, 当然这个 if 不要也可以
  8.     if (p.val == root.val || q.val == root.val) {
  9.         return root;
  10.     }
  11.     if (q.val < root.val) {
  12.         return lowestCommonAncestor(root.left, p, q);
  13.     } else if (p.val > root.val) {
  14.         return lowestCommonAncestor(root.right, p, q);
  15.     } else {
  16.         return root;
  17.     }
  19. }

解法二 迭代

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

  1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2.     int pVal = p.val;
  3.     int qVal = q.val;
  4.     if (pVal == root.val || qVal == root.val) {
  5.         return root;
  6.     }
  7.     // 保持 p.val <= q.val
  8.     if (pVal > qVal) {
  9.         int temp = pVal;
  10.         pVal = qVal;
  11.         qVal = temp;
  12.     }
  13.     while (true) {
  14.         if (qVal < root.val) {
  15.             root = root.left;
  16.         } else if (pVal > root.val) {
  17.             root = root.right;
  18.         } else {
  19.             return root;
  20.         }
  21.     }
  22. }

总

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

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

windliang wechat

添加好友一起进步~

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

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情