# 算法笔记第 04 周

本系列致力于将高频的算法题进行回顾与分析，感兴趣的小伙伴请继续阅读吧。

# 102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

1
2

提示：

树中节点数目在范围 [0, 2000] 内
1000 <= Node.val <= 1000

思路：

二叉树的层序遍历，也就是广度优先遍历。需要借用队列来实现。队列的特点是：先进先出。在JS中，并没有提供原生的队列供我们使用，因此我们需要使用现有的数据结构来实现列表。可以使用数组或者链表的方式实现队列，这里选择使用数组实现。从尾部添加(push)元素，从头部弹出(shift)元素。

具体代码如下：

# BFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    let result = [];
    if (!root) return result; // 如果二叉树为空，则返回空数组
    let queue = [root]; // 初始化队列
    while(queue.length) {
        let temp = [];
        let cur = [];
        while(queue.length) { // 遍历每一层节点
            const node = queue.shift();
            cur.push(node.val);
            if (node.left) temp.push(node.left);
            if (node.right) temp.push(node.right);
        }
        result.push(cur); // 每一层节点值组成的数组
        queue = temp; // 将下一层节点信息赋值给队列
    }
    return result;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 总结

本题的难点在于如何将每层的节点放入一个数组中。当每一层节点刚好遍历完时，队列中所存在的节点刚好就是下一层的所有节点。我们便可以利用这个信息，来通过内层循环处理每一层的节点。

做法就是不断的弹出队头节点，并将节点的值放入cur数组中。如果当前节点有左右子节点，则继续放入队尾，充当下一层的节点。当遍历完当前层节点时，将cur数组放入结果数组当中。同时需要注意，要将内层循环的子节点放入临时数组中，循环结束后再赋值给队列。如果不如此做，内层循环就永远不为空，直到遍历完所有的二叉树节点。最后的结果就是一维数组了。

# 189. 轮转数组

力扣题目链接 (opens new window)

给你一个数组，将数组中的元素向右轮转 k **个位置，其中 k**是非负数。

示例1：

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

1
2
3
4
5
6

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

思路：

首先想到的就是依次将数组末尾的数字弹出，同时放入数组头部，可以写出如下代码：

# pop+unshift

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const length = nums.length;
    if (!k || !length) return nums;
    const step = Math.abs(k % length);
    for (let i = 0; i < step; i++) {
        nums.unshift(nums.pop());
    }
    return nums;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

不幸的是，此方法会超时。因为频繁的弹出和头部插入，会使得数组不断的挪动元素来腾出位置给头部插入的元素。

# splice

本题的难点在于原地修改。如果没有该限制，便可以使用slice进行截取，拼接新数组进行返回即可。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    const length = nums.length;
    if (!k || !length) return nums;
    k = k % length;
    nums.splice(0, 0, ...nums.splice(length - k))
};

1
2
3
4
5
6
7
8
9
10
11

这里使用splice来实现原地修改。首先来复习下splice的用法：

splice() 方法通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组。接受三个参数，分别是：

start。指定修改的开始位置（从0计数）。如果超出了数组的长度，则从数组末尾开始添加内容；如果是负值，则表示从数组末位开始的第几位（从-1计数，这意味着-n是倒数第n个元素并且等价于array.length-n）；如果负数的绝对值大于数组的长度，则表示开始位置为第0位。
deleteCount(可选)。整数，表示要移除的数组元素的个数。如果 deleteCount 大于 start 之后的元素的总数，则从 start 后面的元素都将被删除（含第 start 位）。如果 deleteCount 被省略了，或者它的值大于等于array.length - start(也就是说，如果它大于或者等于start之后的所有元素的数量)，那么start之后数组的所有元素都会被删除。如果 deleteCount 是 0 或者负数，则不移除元素。这种情况下，至少应添加一个新元素。
item1, item2, ...(可选)*。*要添加进数组的元素,从start 位置开始。如果不指定，则 splice() 将只删除数组元素。

返回值：由被删除的元素组成的一个数组。如果只删除了一个元素，则返回只包含一个元素的数组。如果没有删除元素，则返回空数组。

因此，我们需要做的就是删除后面k个元素，同时添加进数组头部。删除后面k个元素，可以通过nums.splice(length - k)实现。删除后会返回被删除元素组成的数组，此时需要插入到数组的头部。因为第三个参数可接收多个值，因此这里通过展开运算符将被删除元素组成的数组展开，从0位置开始，插入到数组中。

# 总结

本题的难点在于原地修改数组，因此这里使用了数组APIsplice来原地修改。

# 107. 二叉树的层序遍历 II

力扣题目链接 (opens new window)

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。

示例1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

1
2

提示：

树中节点数目在范围 [0, 2000] 内
1000 <= Node.val <= 1000

思路：

本题最终的打印顺序刚好和102题顺序相反，因此不难想到，最后将结果数组反转即可。

# BFS+reverse

总体思路和二叉树的层序遍历相同，唯一不同的地方在于将返回的结果进行逆转。102. 二叉树的层序遍历的题解可以看这里 (opens new window)。具体的代码逻辑这里就不赘述了。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    let result = [];
    if (!root) return result; // 如果二叉树为空，则返回空数组
    let queue = [root]; // 初始化队列
    while(queue.length) {
        let temp = [];
        let cur = [];
        while(queue.length) { // 遍历每一层节点
            const node = queue.shift();
            cur.push(node.val);
            if (node.left) temp.push(node.left);
            if (node.right) temp.push(node.right);
        }
        result.push(cur); // 每一层节点值组成的数组
        queue = temp; // 将下一层节点信息赋值给队列
    }
    return result.reverse();
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# DFS

那么除了使用队列的形式进行广度优先遍历以外，还有没有其他方案呢？其实是有的。这里也可以使用深度优先遍历进行求解。具体思路如下：

与普通的DFS不同，这里DFS的时候，需要传递第二个参数，用来表明当前节点的层级。递归的时候维护一个二维数组，确保每一层的节点都存在于同一个数组中，这样就达到了层序遍历的目的。

由于默认深度优先遍历是先处理上层节点的，而本题的要求是从下往上，因此跟广度优先遍历的最终处理一样，需要逆转结果数组并返回即可。

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    let result = [];
    const dep = (node, depth) => {
        if (!node) return;
        result[depth] = result[depth] || [];
        result[depth].push(node.val);
        dep(node.left, depth + 1)
        dep(node.right, depth + 1)
    }
    dep(root, 0);
    return result.reverse();
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 总结

本题是二叉树的层序遍历的衍生版本。分别使用了BFS和DFS进行求解。

# 105. 从前序与中序遍历序列构造二叉树

力扣题目链接 (opens new window)

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例1：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

1
2

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

思路：

本题考查前序和中序遍历的特点。

前序遍历：根左右
中序遍历：左根右

我们通过前序遍历可以找到二叉树的根。根据中序遍历，我们可以知道根的左右子树的中序遍历及左右子树节点数目。知道左右子树的节点数目，结合前序遍历，我们就知道左右子树的前序遍历。

然后结合左右子树的前序和中序遍历，递归的构造左右子树为当前构造出节点的左右子树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length) return null; // 二叉树为空
    const root = preorder[0]; // 从前序遍历获取根节点
    const node = new TreeNode(root); // 通过根节点构造节点
    const index = inorder.indexOf(root); // 从中序遍历获取根节点的索引
    const inLeft = inorder.slice(0, index); // 中序遍历的左子树
    const inRight = inorder.slice(index + 1); // 中序遍历的右子树
    const preLeft = preorder.slice(1, index + 1); // 前序遍历的左子树
    const preRight = preorder.slice(index + 1); // 前序遍历的右子树
    node.left = buildTree(preLeft, inLeft); // 递归构造左子树
    node.right = buildTree(preRight, inRight); // 递归构造右子树
    return node; // 返回构造出的节点
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 总结

本题需要结合前序遍历和中序遍历，来将二叉树拆分为左子树、根、右子树三个部分。找出根节点就调用构造函数构造出新节点，左右子树分别有前序遍历和中序遍历两个顺序，然后递归调用函数进而找到左子树的根节点，以及右子树的根节点。这两个根节点恰好就是刚才构造出的新节点的左右子节点，这样便可以递归的构造出一个完整的二叉树。

最终返回根节点即可。

# 104. 二叉树的最大深度

力扣题目链接 (opens new window)

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5

返回它的最大深度 3 。

思路：

本题可采用递归的思路进行题解。要求出二叉树的最大深度，可以求出左右子树的最大深度，找到较大者并且加一便是二叉树本身的最大深度。递归终止条件是：如果当前节点为空，则返回0，没有节点说明深度为0。

# 递归

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

1
2
3
4
5
6
7
8

# 645. 错误的集合

力扣题目链接 (opens new window)

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：

输入：nums = [1,2,2,4]
输出：[2,3]

1
2

提示：

2 <= nums.length <= 10^4
1 <= nums[i] <= 10^4

思路：

最容易想到的是使用哈希表存储所有的元素。由于元素范围是[1, n]，因此循环1~n，判断当前元素是否存在于哈希表中，如果存在且重复，则是结果数组的第一项，如果不存在，则是结果数组的第二项。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    let map = new Map();
    let length = nums.length;
    let res = [];
    for (const num of nums) {
        map.set(num, map.has(num) ? 2 : 1);
    }
    for (let i = 1; i <= length; i++) {
        const count = map.get(i) || 0;
        if (count === 2) res[0] = i;
        if (count === 0) res[1] = i;
    }
    return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 236. 二叉树的最近公共祖先

力扣题目链接 (opens new window)

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

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

示例1：

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

1
2
3

提示：

树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同。
p != q
p 和 q 均存在于给定的二叉树中。

思路：

本题与剑指 Offer 68 - II. 二叉树的最近公共祖先 (opens new window)属于同一题，鉴于已经做过题解，这里直接给出具体代码。

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (!root || root === p || root === q) return root; // 递归终止条件
    let left = lowestCommonAncestor(root.left, p, q); // 缓存左子树结果
    let right = lowestCommonAncestor(root.right, p, q); // 缓存右子树结果
    if (!left) return right; // 分别是上面的四种情况
    if (!right) return left;
    return root;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 110. 平衡二叉树

力扣题目链接 (opens new window)

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

示例1：

输入：root = [3,9,20,null,null,15,7]
输出：true

1
2

提示：

树中的节点数在范围 [0, 5000] 内
-10^4 <= Node.val <= 10^4

思路：

本题与剑指 Offer 55 - II. 平衡二叉树 (opens new window)属于同一题，可以点击链接查看题解。这里直接给出代码：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const recur = (node) => {
    if (!node) return 0; // 当前节点不存在，则深度为0
    let left = recur(node.left);
    if (left === -1) return -1; // 左子树为-1，则提前返回
    let right = recur(node.right);
    if (right === -1) return -1; // 右子树为-1，则提前返回
    return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}

const isBalanced = (root) => {
    return recur(root) !== -1; // 判断递归返回值是否为-1
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 112. 路径总和

力扣题目链接 (opens new window)

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点是指没有子节点的节点。

示例1：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

1
2
3
4
5
6

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

思路：

本题采用递归的思路实现。

# 递归

递归终止条件是，如果当前节点为空，则直接返回false。如果当前节点存在，但是不存在左右子节点，其实就是叶子节点。则判断当前节点的值是否等于第二个参数目标值。如果相等，则意味着存在这么一条路径，否则表示此路不通。

如果当前节点不是叶子节点，那么就递归处理左右子节点。此时需要将第二个参数减去当前节点的值，更新目标值，方便后续判断。这里采用短路运算进行递归，只要找到一条路径，则提前返回。

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    if (!root.left && !root.right) return root.val === targetSum;
    targetSum = targetSum - root.val;
    return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};

1
2
3
4
5
6
7
8
9
10
11

算法笔记第 04 周剑指Offer题解-Day1