队列(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
|
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; };
|