javascript-leetcode
javascript-leetcode copied to clipboard
Geekhyt
LeetCode 题解仓库🍖
[原题链接](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-iqd5/) ## 递归 dfs ```javascript const serialize = function(root) { const res = [] function dfs(node) { if (node === null) { res.push(null) return } res.push(node.val) dfs(node.left) dfs(node.right) } dfs(root)...
[原题链接](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-eoky/) ## 递归 dfs 1.从根节点开始遍历，递归左右子树 2.递归终止条件：当前节点为空或者等于 p 或 q，返回当前节点 3.p，q 可能在相同的子树中，也可能在不同的子树中 4.如果左右子树查到节点都不为空，则表示 p 和 q 分别在左右子树中，当前节点就是最近公共祖先 5.如果左右子树中有一个不为空，则返回为空节点 ```javascript const lowestCommonAncestor = function(root, p, q) { if (root === null ||...
[原题链接](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-bwev/) ## 递归 dfs 1. root 为空时，高度为 0 2. root 的左右子树都为空时，高度为 1 3. 如果左子树或者右子树为空时，返回另一棵子树的高度 4. 否则返回两棵子树的高度最小值 ```javascript const minDepth = function(root) { if (root === null) return 0 if (root.left...
[原题链接](https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-6gok/) ## 递归 dfs ```javascript const preorder = function(root) { if (root === null) return [] const res = [] function dfs(root) { if (root === null) return res.push(root.val) for...
[原题链接](https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-dpjn/) ## 递归 dfs ```javascript const postorder = function(root) { if (root === null) return [] const res = [] function dfs(root) { if (root === null) return; for (let...
[原题链接](https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-u2td/) ## 队列 bfs 使用队列进行广度优先遍历，level 数组存放当前层级的值，处理完一层后推入结果数组 result。 ```javascript const levelOrder = function(root) { if (root == null) return [] const result = [] const queue = [root] while (queue.length >...
[原题链接](https://leetcode-cn.com/problems/contains-duplicate/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-1d58/) ## 排序 排序后看相邻两位的数字 ```js const containsDuplicate = function(nums) { nums.sort((a, b) => a - b) const n = nums.length for (let i = 0; i < n - 1;...
[原题链接](https://leetcode-cn.com/problems/merge-two-binary-trees/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-09mj/) ## dfs 递归 在 root1 上直接修改，将两个树对应的节点相加后，赋值给 root1，然后递归执行两个左右子树。 ```js const mergeTrees = function(root1, root2) { const preOrder = function(root1, root2) { if (!root1) return root2 if (!root2) return root1 root1.val...
[原题链接](https://leetcode-cn.com/problems/lru-cache/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-60to/) ## 借用 Map Map 的键值是有序的，可以按照插入的顺序返回键值。 1. 元素存在就将其更新 2. `this.cache.keys().next().value`: 获取到头部元素(也就是最远使用的元素)的 key ```js const LRUCache = function(capacity) { this.cap = capacity this.cache = new Map() } LRUCache.prototype.get = function(key) {...
[原题链接](https://leetcode-cn.com/problems/binary-search/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-36k8/) ## 二分查找 理解二分算法可以参考：[二分查找详解](https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/) ```js // 左闭右闭区间 const search = function(nums, target) { let start = 0 let end = nums.length - 1 while (start > 1) if (nums[mid] ===...