面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
数学
数组
链表
二叉树
最小栈、Shuffle an Array和将有序数组转换为二叉搜索树
对称二叉树、二叉树的最大深度和验证二叉搜索树
二叉树的层次遍历、二叉树的序列化与反序列化和常数时间内插入删除、获得随机数
中序遍历二叉树、从前序与中序遍历序列构造二叉树和二叉搜索树中第 K 小的元素
填充每个节点的下一个右侧节点指针、岛屿数量和二叉树的锯齿形层次遍历
动态规划
回溯算法
排序与搜索
栈和队列
结束篇
由 GitBook 提供支持
二叉树的层次遍历、二叉树的序列化与反序列化和常数时间内插入删除、获得随机数

二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
示例
给定二叉树: [3,9,20,null,null,15,7]
​
3
/ \
9 20
/ \
15 7
​
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

方法一 递归

思路
最简单的解法就是递归，首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。
详解
  1. 1.
    输出列表称为 levels，当前最高层数就是列表的长度 len(levels)。比较访问节点所在的层次 level 和当前最高层次 len(levels) 的大小，如果前者更大就向 levels 添加一个空列表;
  2. 2.
    将当前节点插入到对应层的列表 levels[level] 中;
  3. 3.
    递归非空的孩子节点：helper(node.left / node.right, level + 1)。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
const levelOrder = function (root) {
const levels = [];
if (!root) {
return levels;
}
const helper = function (node, level) {
if (levels.length === level) {
levels.push([]);
}
levels[level].push(node.val);
if (node.left) {
helper(node.left, level + 1);
}
if (node.right) {
helper(node.right, level + 1);
}
};
helper(root, 0);
return levels;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    因为每个节点恰好会被运算一次。
  • 空间复杂度：
    O(n)O(n)
    ​
    保存输出结果的数组包含
    nn
     个节点的值。

方法二 迭代

思路
我们将树上顶点按照层次依次放入队列结构中，队列中元素满足 FIFO（先进先出）的原则。使用了 js 中的 push 和 shift 方法
第 0 层只包含根节点 root ，算法实现如下：
初始化队列只包含一个节点 root 和层次编号 0 ： level = 0。 当队列非空的时候：
  • 在输出结果 levels 中插入一个空列表，开始当前层的算法。
  • 计算当前层有多少个元素：等于队列的长度。
  • 将这些元素从队列中弹出，并加入 levels 当前层的空列表中。
  • 将他们的孩子节点作为下一层压入队列中。
  • 进入下一层 level++。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
const levelOrder = function (root) {
const levels = [];
if (!root) {
return levels;
}
​
let level = 0;
const queue = [root];
while (queue.length) {
// 开始当前层级的循环
levels.push([]);
// 获取当前level的长度
const levelLength = queue.length;
​
for (let i = 0; i < levelLength; i++) {
const node = queue.shift();
// 给当前level添加值
levels[level].push(node.val);
​
// 给当前level添加子节点
// 并加入队列，给下一个level使用
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
​
// 进入下一个level
level += 1;
}
​
return levels;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​

二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例
你可以将以下二叉树：
​
1
/ \
2 3
/ \
4 5
​
序列化为 "[1, 2, 3, null, null, 4, 5]"

方法一 深度优先遍历(DFS)

思路
遍历二叉树：L、D、R 分别表示遍历左子树、访问根结点和遍历右子树。先序遍历二叉树的顺序是 DLR，中序遍历二叉树的顺序是 LDR，后序遍历二叉树的顺序是 LRD。 深度优先遍历包含先序、中序、后序遍历。先序遍历的顺序：先访问根节点，再遍历左节点，最后遍历右节点。为了能够反序列化，在遍历的时候需要将 null 也保存进去。伪代码如下：
visit(node)
print node.value
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)
示例中的二叉树以本算法先序遍历后的结果为：[1,2,null,null,3,4,null,null,5,null,null] 反序列化：将先序遍历的结果按根节点、左子树、右子树顺序复原，伪代码如下：
structure();
node = new TreeNode();
node.left = structure();
node.right = structure();
详解
  1. 1.
    首先序列化二叉树，定义一个遍历方法，先访问根节点，再遍历左节点，最后遍历右节点，将 null 也保存进数组中
  2. 2.
    反序列化二叉树，将数组还原回二叉树，因为数组是先序遍历的结果，遍历数组，然后按照根节点、左子树、右子树顺序复原二叉树
/**
* 二叉树节点构造函数
* @param {string} val 节点值
*/
function TreeNode (val) {
this.val = val;
this.left = this.right = null;
}
​
/**
* 序列化二叉树，将二叉树转成数组
* @param {TreeNode} root
*/
const serialize = function (root) {
const result = [];
// 遍历节点
function traverseNode (node) {
if (node === null) {
result.push(null);
} else {
// 先序遍历，先访问根节点，再遍历左节点，最后遍历右节点
result.push(node.val);
traverseNode(node.left);
traverseNode(node.right);
}
}
​
traverseNode(root);
return result;
};
​
/**
* 反序列化二叉树，将数组还原回二叉树
* @param {string} data
*/
const deserialize = function (data) {
const length = data.length;
if (length === 0) {
return null;
}
let i = 0;
// data 结构化成树
function structure () {
if (i >= length) {
return null;
}
const val = data[i];
i++;
if (val === null) {
return null;
}
const node = new TreeNode(val);
node.left = structure();
node.right = structure();
​
return node;
}
return structure();
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​
    serialize 方法为 result 分配了空间，递归中没有产生新的对象，空间复杂度为
    O(1)O(1)
     deserialize 方法每次遍历会 new 一个对象，空间复杂度为
    O(n)O(n)
    ​

方法二 广度优先遍历(BFS)

示例中的二叉树以本算法广度优先(层序)遍历后的结果为：[1,2,3,null,null,4,5]
思路
序列化：广度优先遍历序列化二叉树是按层级从上往下将每层节点从左往右依次遍历，用队列来处理遍历，先将根节点入队，然后根节点出队，再左子树和右子树入队，递归遍历即可。 反序列化：从序列化好的数组中取第一个元素，生成根节点。将根节点放入队列。循环队列，根节点的左右子树分别放入队列，循环此操作，直到队列为空。
详解
序列化： 1. 定义一个 result 数组存放序列化结果 1. 定义一个 queue 数组，作为队列 2. 将根节点入队 3. 循环队列，队列中的第一个元素(节点)出队，将此节点值 push 进 result 数组。分别将此节点左右节点入队 4. 当队列为空时，跳出循环 5. 返回 result
反序列化： 1. 从 result 取出第一个节点值，生成根节点放到队列中 2. 循环队列，队列中第一个元素(节点)出队，从 result 取出下一个值还原左节点，将此左节点入队，从 result 取出下一个值还原右节点，将此右节点入队 3. 当 result 或队列为空时，跳出循环 4. 返回反序列化好的节点(根节点)
/**
* 二叉树节点构造函数
* @param {string} val 节点值
*/
function TreeNode (val) {
this.val = val;
this.left = this.right = null;
}
​
/**
* 序列化二叉树，将二叉树转成数组
* @param {TreeNode} root
*/
const serialize = function (root) {
if (!root) {
return [];
}
const result = [];
const queue = [];
queue.push(root);
let node;
while (queue.length) {
node = queue.shift();
result.push(node ? node.val : null);
if (node) {
queue.push(node.left);
queue.push(node.right);
}
}
return result;
};
​
/**
* 反序列化二叉树，将数组还原回二叉树
* @param {string} data
*/
const deserialize = function (data) {
const length = data.length;
if (length === 0) {
return null;
}
// 取出第一个节点值，生成根节点放到队列中
const root = new TreeNode(data.shift());
const queue = [root];
while (queue.length) {
// 取出将要复原的节点
const node = queue.shift();
// 节点遍历完，跳出循环
if (data.length === 0) {
break;
}
// 先还原左节点
const leftVal = data.shift();
if (leftVal === null) {
node.left = null;
} else {
node.left = new TreeNode(leftVal);
// 将生成的左节点放入队列，下次循环会复原此左节点的子节点
queue.push(node.left);
}
// 节点遍历完，跳出循环
if (data.length === 0) {
break;
}
// 还原右节点
const rightVal = data.shift();
if (rightVal === null) {
node.right = null;
} else {
node.right = new TreeNode(rightVal);
// 将生成的右节点放入队列，下次循环会复原此左节点的子节点
queue.push(node.right);
}
}
​
return root;
};
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    serialize 方法中每个节点遍历一次，时间复杂度为
    O(n)O(n)
     deserialize 方法遍历
    nn
     次，
    nn
     为 data 的长度，时间复杂度为
    O(n)O(n)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​
    serialize 方法为 result 分配了空间，递归中没有产生新的对象，空间复杂度为
    O(1)O(1)
    deserialize 方法每次遍历会 new 一个对象，空间复杂度为
    O(n)O(n)
    ​

常数时间内插入删除、获得随机数

设计一个支持在平均 时间复杂度
O(1)O(1)
 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 val 存在时，从集合中移除该项。 getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
​
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
​
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
​
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
​
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
​
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
​
// 2 已在集合中，所以返回 false 。
randomSet.insert(2);
​
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

方法一 Array + Object(Map)

思路
使用动态数组存储元素值，对象存储值到索引的映射；有索引可以实现常数时间的 insert 和 getRandom。remove 的常数时间则使用：总是删除最后一个元素，将要删除元素和最后一个元素交换，然后将最后一个元素删除来实现。
详解
  1. 1.
    insert: 添加元素到动态数组, 并在对象中添加值到索引的映射关系。
  2. 2.
    remove: 在对象中查找要删除元素的索引，将要删除元素与最后一个元素交换，删除最后一个元素，更新对象中的对应关系。
  3. 3.
    getRandom: 借助 random 函数，获取下标范围内的整数，然后取出数组对应下标元素。
/**
* Initialize your data structure here.
*/
const RandomizedSet = function () {
this.arr = [];
this.values = {};
};
​
/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
if (this.values[val] >= 0) {
return false;
} else {
this.values[val] = this.arr.length;
this.arr.push(val);
return true;
}
};
​
/**
* Removes a value from the set. Returns true if the set contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
const i = this.values[val];
const l = this.arr.length;
if (i >= 0) {
this.values[this.arr[l - 1]] = i;
this.values[val] = -1;
this.arr.splice(i, 1, this.arr[l - 1]);
this.arr.pop();
return true;
} else {
return false;
}
};
​
/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
const l = this.arr.length;
const i = Math.floor(Math.random() * l);
return this.arr[i];
};
​
/**
* Your RandomizedSet object will be instantiated and called as such:
* var obj = new RandomizedSet()
* var param_1 = obj.insert(val)
* var param_2 = obj.remove(val)
* var param_3 = obj.getRandom()
*/
复杂度分析
  • 时间复杂度：
    O(1)O(1)
    ​
    getRandom 时间复杂度为
    O(1)O(1)
    ，insert 和 remove 平均时间复杂度为
    O(1)O(1)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​
    存储了 n 个元素信息
以前
对称二叉树、二叉树的最大深度和验证二叉搜索树
下一个
中序遍历二叉树、从前序与中序遍历序列构造二叉树和二叉搜索树中第 K 小的元素
最近更新 2yr ago
复制链接
大纲
二叉树的层次遍历
二叉树的序列化与反序列化
常数时间内插入删除、获得随机数