0%

队列(queue)

队列(queue)

定义

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。
先进先出

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Queue() {
this.data = new Array();
this.clear = function(){
this.data = new Array();
}
this.shift = function () {
return this.data.shift();
}
this.push = function (d) {
this.data.push(d);
}
this.getItem = function(){
return this.data[0];
}
}

应用

108.将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

0
/ \
-3 9
/ /
-10 5

实现

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
* 解法: 分治法
* 思路:搜索数组的中位作为根节点构建二叉树,原数组去掉中位数之后生成两个数组,继续寻找中位数作为子树的根节点。
* 细节:采用一个队列来维护 数组在顺序 采用这个树顺序的数组,从根节点直接写入树,相对来说降低了setTreeNode方法的难度,但需要维护一个队列。
*/
var sortedArrayToBST = function (nums) {
if (nums.length === 0) {
return null;
}
// 一些节点操作方法
function Node(start, end) {
this.start = start;
this.end = end;
}
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function setTreeNode(val, tree) {
if (tree.left === null && tree.val > val) {
tree.left = new TreeNode(val);
}
else if (tree.right === null && tree.val < val) {
tree.right = new TreeNode(val);
}
else if (tree.left !== null && tree.val > val) {
setTreeNode(val, tree.left);
}
else if (tree.right !== null && tree.val < val) {
setTreeNode(val, tree.right);
}
}

const len = nums.length;
let lenList = [];
let lenQueue = [new Node(0, len - 1)];

while (lenQueue.length) {
let node = lenQueue.shift();
if (node.end - node.start > 1) {
lenQueue.push(new Node(node.start, Math.round((node.end + node.start) / 2) - 1));
lenQueue.push(new Node(Math.round((node.end + node.start) / 2) + 1, node.end));
} else if (node.end - node.start === 1) {
lenQueue.push(new Node(node.start, Math.round((node.end + node.start) / 2) - 1));
}
lenList.push(Math.round((node.end + node.start) / 2));
}

let tree = new TreeNode(nums[lenList[0]]);

for (let i = 1; i < lenList.length; i++) {
setTreeNode(nums[lenList[i]], tree);
}
return tree;
};