数据结构

树 树是一种常用的数据结构，用来模拟具有树状结构性质的数据集合 树的每一个节点有一个根植和一个包含所有子节点的列表。 二叉树 二叉树是一种更为典型的树状结构。二叉树每个节点最多具有两个子树，通常子树称为“左子树”和“右子树” 二叉树前序遍历 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树（根节点 -> 左子树 -> 右子树） 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ // 递归 const preorderTraversal = function(root) { let result = [] function fn(root){ if(root !== null){ result.push(root.val) if(root.left) fn(root.left) if(root.right) fn(root.right) } } fn(root) return result }; 二叉树中序遍历 先遍历左子树，然后访问根节点，最后遍历右子树（左子树 -> 根节点 -> 右子树） 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ const inorderTraversal = function(root) { let result = [] function fn(root){ if(root !== null){ if(root.left) fn(root.left) result.push(root.val) if(root.right) fn(root.right) } } fn(root) return result }; 二叉树后序遍历 先遍历左子树，然后遍历右子树，最后访问根节点（左子树 -> 右子树 -> 根节点） 算法 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ const postorderTraversal = function(root) { let result = [] function fn(root){ if(root !== null){ if(root.left) fn(root.left) if(root.right) fn(root.right) result.push(root.val) } } fn(root) return result }; 二叉树层序遍历 算法： /** * 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) { let levels = [] if(root === null) return levels function fn(node, level){ let len = levels.length if(len === level) levels.push([]) levels[level].push(node.val) if(node.left) fn(node.left, level+1) if(node.right) fn(node.right, level+1) } fn(root, 0) return levels }; 二叉树最大深度 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { // 写递归的一个重要思路就是相信这个函数能完成任务，此题带有动态规划的感觉 // 最大深度 = 1+Math.max(根节点的左子树最大深度, 根节点的右子树最大深度) // 根节点的左子树最大深度 = 1 + Math.max(左子树的左子树最大深度, 左子树的右子树最大深度) // 根节点的右子树最大深度 = 1 + Math.max(右子树的左子树最大深度, 右子树的右子树最大深度) if(!root){ return 0 }else{ return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 } }; 对称二叉树 给定一个二叉树，检查它是否是镜像对称的。 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { return isMirroTree(root, root) }; function isMirroTree(root_1, root_2){ if(root_1 === null && root_2 === null) return true if(root_1 === null || root_2 === null) return false return (root_1.val === root_2.val) && isMirroTree(root_1.left, root_2.right) && isMirroTree(root_1.right, root_2.left) } 路径总和 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {number} sum * @return {boolean} */ var hasPathSum = function(root, sum) { return helper(root, sum) }; function helper(node, sum){ if(!node){ return false }else{ sum -= node.val } if(!node.left && !node.right){ return sum === 0 } return helper(node.left, sum) || helper(node.right, sum) }

链表的区别 链表也分为单链表和双链表。 单链表：每个节点包含 value 和 next，next 指向下一个节点 双链表：每个节点包含 prev、value 和 next，prev 指向前一个节点，next 指向下一个节点 单链表的实现 class Node{ constructor(value){ this.value = value this.next = null } } class MyLinkedList{ constructor(){ this.head = null this.length = 0 } // 按索引获取节点 value get(index){ if(index >= 0 && index < this.length){ let current = this.head if(index === 0){ return current.value }else{ let position = 0 while(position < index){ current = current.next position++ } return current.value } } return -1 } // 在头部添加节点 addAtHead(val){ const node = new Node(val) let current = this.head this.head = node this.head.next = current this.length++ } // 添加节点到尾部 addAtTail(val){ const node = new Node(val) if(this.length){ let current = this.head while(current.next){ current = current.next } current.next = node }else{ this.head = node } this.length++ } // 在给定位置添加节点 addAtIndex(index, val){ const node = new Node(val) let position = 0 let current = null let previous = null let length = this.length if(length === 0 && index <= 0){ this.head = node this.length++ }else if (index <= 0){ this.addAtHead(val) }else if(index === length){ this.addAtTail(val) }else if(index > 0 && index < length){ current = this.head while(position < index){ previous = current current = current.next position++ } previous.next = node node.next = current this.length++ } } // 按索引删除 deleteAtIndex(index){ if(index >= this.length) return let current = this.head let previous = null let position = 0 if(index === 0 && index === this.length){ this.head = null }else if(index === 0 ){ this.head = current.next }else{ while(position < index){ previous = current current = current.next position++ } previous.next = current.next } this.length-- } } 双链表的实现 class Node{ constructor(value){ this.value = value this.next = null this.prev = null } } class MyLinkedList{ constructor(){ this.head = null this.length = 0 } get(index){ if(index >= 0 && index < this.length){ let current = this.head if(index === 0){ return current.value }else{ let position = 0 while(position < index){ current = current.next position++ } return current.value } } return -1 } addAtHead(val){ const node = new Node(val) let current = this.head this.head = node this.head.next = current this.length++ if(this.length === 1){ return }else{ current.prev = this.head } } addAtTail(val){ const node = new Node(val) if(this.length){ let current = this.head while(current.next){ current = current.next } current.next = node node.prev = current }else{ this.head = node } this.length++ } addAtIndex(index, val){ const node = new Node(val) let position = 0 let current = null let previous = null let length = this.length if(length === 0 && index <= 0){ this.head = node this.length++ }else if (index <= 0){ this.addAtHead(val) }else if(index === length){ this.addAtTail(val) }else if(index > 0 && index < length){ current = this.head while(position < index){ previous = current current = current.next position++ } previous.next = node current.prev = node node.prev = previous node.next = current this.length++ } } deleteAtIndex(index){ if(index >= this.length) return let current = this.head let previous = null let position = 0 if(index === 0 && this.length === 1){ this.head = null }else if(index === 0){ this.head = current.next current.next.prev = null }else{ while(position < index){ previous = current current = current.next position++ } if(index === this.length - 1){ previous.next = null }else{ previous.next = current.next current.next.prev = previous } } this.length-- } } 环形链表 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 ...

栈 栈是一种线性数据结构，其修改顺序是后进先出(last in first out)，因此也被成为 LIFO表。 在现实生活中可以映射到我们堆叠在桌子上的书、餐具柜中队列的餐盘之类。 我们可以用数组模拟栈： class Static{ constructor(){ this.items = [] } // 检查栈是否为空 get isEmpty(){ return !this.items.length } // 获取栈的长度 get size(){ return this.items.length } // 查看栈顶 get top(){ return this.items[this.items.length - 1] } // 入栈 push(val){ this.items.push(val) return this.items } // 出栈 pop(){ return this.items.pop() } // 清空栈 clear(){ this.items.length = [] return this.items } } 队列 与栈相反，队列是修改顺序是先进先出(first in first out)，称为 FIFO表。 在现实生活中可以映射到点餐队列、打印队列。 用数组模拟队列： class Queue{ constructor(){ this.items = [] } // 检查队列是否为空 get isEmpty(){ return !this.items.length } // 获取队列的长度 get size(){ return this.items.length } // 获取首元素 get first(){ return this.items[0] } // 获取尾元素 get last(){ return this.items[this.items.length - 1] } // 入队 enqueue(val){ this.items.push(val) return this.items } // 出队 dequeue(){ return this.items.shift() } // 清空队列 clear(){ this.items.length = 0 } }