【带你重刷剑指 Offer 系列】第 19 天 搜索与回溯算法（中等）三题题解一览

🧨 大家好，我是 Smooth，一名大二的 SCAU 前端er
🏆 本篇文章会对剑指 offer 系列的第19天搜索与回溯算法（中等）三道题做详解
🙌 如文章有误，恳请评论区指正，谢谢！

原文章链接

剑指 Offer 64. 求1+2+…+n

一、题目描述：

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

原题链接：剑指 Offer 64. 求1+2+…+n

二、题目要求：

例子

示例 1：
输入: n = 3
输出: 6

示例 2：
输入: n = 9
输出: 45

考察内容

通过逻辑运算符的短路效应来终止递归

三、思路分析

这道题考察的思想

在不使用我们平时做题常用的各种语句的前提下（包括乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）），完成这道不常见的题目。

我的思路

1. 这道题常用的方法就是递归，同样递归确实在思想上是最简单的，但常见递归思路在这题会被卡住，因为我们平时都会通过 if 语句来判断递归终止条件，但此题不能用。

2. 既然不能使用上面的那些语句，那平时我写代码时还用到什么语句来进行条件判断呢？

3. 答案一下就想到了，没错，就是用逻辑运算符，通过其短路效应来做条件判断进行递归终止。

逻辑运算符的短路效应

常见的逻辑运算符有三种，即 “与 && ”，“或 || ”，所谓的短路效应，如下：

• if(A && B) 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false；

• if(A || B) 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true

因此，本题需要实现 “当 n = 1时终止递归” 的需求，可通过短路效应实现。

四、代码讲解

当 num = 1 时 num > 1 不成立 ，此时 “短路” ，终止后续递归，即：

num > 1 && sum(num - 1)

更详细解释

通过 num 值判断要不要继续递归，类似于之前的 if，只不过不同之处是 if 判断为 false 直接返回，函数内后面的语句都不执行，此处 && 只是决定还要不要继续递归，后面的还是会执行

五、AC 代码

代码

/**
 * @param {number} n
 * @return {number}
 */
var sumNums = function(n) {
    let res = 0;
    const sum = (num) => {
        // 通过 num 值判断要不要继续递归，类似于之前的 if，只不过不同之处是 if 判断为 false 直接返回，后面的都不执行，此处 && 只是决定还要不要继续递归，后面的还是会执行
        num > 1 && sum(num - 1);
        res += num;
        return res;
    }
    sum(n);
    return res;
};

时间和空间复杂度

六、总结

这题的思维比较跳跃，要求我们跳出常用的语句，用比较难想到的逻辑运算符配合递归求解，总体来说，就是多做题多领略到不同题目的风采吧~

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

一、题目描述：

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

原题链接：剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

二、题目要求：

例子

例如，给定如上二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

考察内容

二叉搜索树性质 + 迭代

三、思路分析

这道题考察的思想

了解二叉搜索树这个数据结构，并能通过该结构特质简化此题的求解思路

二叉搜索树性质：对于根节点来说，节点的左子树的所有值都比当前节点要小，节点的右子树的所有值都比当前节点要大

我的思路

本题给定了两个重要条件：

1. 树为二叉搜索树
2. 树的所有节点的值都是唯一的。

根据 二叉搜索树的性质，可以通过迭代对二叉搜索树进行 DFS

• 如果 p 和 q 对应的值都比当前节点要大，那么说明应该往右子树继续迭代
• 如果 p 和 q 对应的值都比当前节点要小，那么说明应该往左子树继续迭代
• 如果 p 和 q 对应的值一个比当前节点要大，一个要小，说明开始出现分岔了，指针不能单纯地往左子树或右子树继续遍历了，此时就是 p 和 q 的最近公共祖先
  即：
• 若 root.val < p.val，则 p 在 root 右子树 中；
• 若 root.val > p.val，则 p 在 root 左子树 中；
• 若 root.val = p.val，则 p 和 root 指向同一节点；
  
  
  

  四、代码讲解

1. 循环搜索： 当节点 now 为空时跳出；
2. 当 p, q 都在 now 的 右子树 中，则遍历至 now.right；
3. 当 p, q 都在 now 的 左子树 中，则遍历至 now.left；
4. 否则，说明找到了 最近公共祖先，跳出（第一种情况 p 或 q 跟根节点值相同，第二种情况一个比根节点值小，一个大）。
5. 返回值： 最近公共祖先 now 。
   
   
   

   五、AC 代码

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    let now = root;
    while(now) {
        // 说明 now 指针应该往右子树指，因为要找的两个节点值都比当前根节点值要大
        if(now.val < p.val && now.val < q.val) {
            now = now.right;
        } else if(now.val > p.val && now.val > q.val) {
            // 说明 now 指针应该往左子树指，因为要找的两个节点值都比当前根节点值要小
            now = now.left;
        } else {
            // p 和 q 的值一大一小，说明当前节点就是最近公共祖先了，因为出现分岔了
            break;
        }
    }
    return now;
};

时间和空间复杂度

六、总结

此题要求我们要了解二叉搜索树这个数据结构，并能通过该结构特质简化递归的求解思路

剑指 Offer 68 - II. 二叉树的最近公共祖先

一、题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

原题链接：剑指 Offer 68 - II. 二叉树的最近公共祖先

二、题目要求：

例子

例如，给定如上二叉搜索树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

考察内容

先序遍历 + 回溯

三、思路分析

这道题考察的思想

了解最近公共祖先的意思，并知道有哪几种情况符合

我的思路

首先明确何为最近公共祖先？

若 root 是 p 和 q 的 最近公共祖先 ，则只可能为以下情况之一：

• p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
• p = root ，且 q 在 root 的左或右子树中；
• q = root ，且 p 在 root 的左或右子树中；

思路

1. 使用先序遍历方法对二叉树进行递归遍历，当遇到节点 p 或 q 时直接返回。
2. 从底至顶回溯，当节点 p, q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root。
   
   
   

   四、代码讲解

   对于递归

终止条件

• 当越过叶节点，则直接返回 null ；
• 当 root 等于 p, q ，则直接返回 root；

返回值

• 首先，对左子树继续进行递归，返回值记为 left；对右子树继续进行递归，返回值记为 right；
• 然后，根据 left 和 right，可展开为四种情况：
• 当 left 和 right 同时为空 ：说明 root 的左右子树中都不包含 p,q，返回 null 即可；
• 当 left 为空 ，right 不为空（或反过来） ：p,q 都不在 root 的左子树中，直接返回 right，对于该情况，还可以细分为两种情况：
  • （1） p 或 q 其中一个在 root 的 右子树 中，假设此时根节点是 p，则 right 指向的就是 q；
  • （2） p,q 两节点都在 root 的 右子树 中，此时的 right 指向的就是最近公共祖先节点；
• 当 left 和 right 同时不为空 ：说明 p, q 分列在 root 的 两侧，因此 root 为最近公共祖先，返回 root ；
  
  
  

  五、AC 代码

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    return dfs(root, p, q);
};

const dfs = (root, p, q) => {
    // 如果结点为空，或结点直接等于 p 或 q 了，直接返回该结点即可(相当于返回空，或 p 或 q)
    if(!root || root === p || root === q) return root;

    let left = dfs(root.left, p, q);
    let right = dfs(root.right, p, q);

    if(!right && !left) {
        return null;
    }else if(!left && right) {
        return right;
    } else if(!right && left) {
        return left;
    }
    return root;
}

时间和空间复杂度

六、总结

此题要求我们要了解有哪几种情况符合最近公共祖先，并能通过回溯按指定条件进行返回值

最后

这是我 「LeetCode」 系列文章的第 `No.1 篇，系列开始于 2022/03/01。

在这个系列文章里面，除了会理清解题思路，尽量给出多种解题方式以外，还会探讨本题所涉及的知识点。

我会争取每日 2 题，每日一更，所有的题解均收录于该仓库：【LeetCode】系列

目前仓库正在加紧更新题解中哈哈，觉得不错的小伙伴可以点个 star 支持一下

写作不易，「点赞」+「收藏」+「转发」 谢谢支持❤

往期推荐

《都2022年了还不考虑来学React Hook吗？6k字带你从入门到吃透》

《一份不可多得的 Webpack 学习指南（1万字长文带你入门 Webpack 并掌握常用的进阶配置）》

《Github + hexo 实现自己的个人博客、配置主题（超详细）》

《10分钟让你彻底理解如何配置子域名来部署多个项目》

《一文理解配置伪静态解决 部署项目刷新页面404问题

《带你3分钟掌握常见的水平垂直居中面试题》

《React实战：使用Antd+EMOJIALL 实现emoji表情符号的输入》

《【建议收藏】长达万字的git常用指令总结！！！适合小白及在工作中想要对git基本指令有所了解的人群》

《浅谈javascript的原型和原型链(新手懵懂想学会原型链？看这篇文章就足够啦！！！)》