javascript-leetcode
javascript-leetcode copied to clipboard
Geekhyt
LeetCode 题解仓库🍖
[原题链接](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-pgjc/)  前序遍历：先打印当前节点，再打印当前节点的左子树，最后打印当前节点的右子树 (ABCDEFG) ```javascript const preorderTraversal = function(root) { const result = []; function pushRoot(node){ if (node !== null) { result.push(node.val); if (node.left !== null){ pushRoot(node.left); } if (node.right...
[原题链接](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-2k93/)  后序遍历：先打印当前节点的左子树，再打印当前节点的右子树，最后打印当前节点 (CDBFGEA)。 ```javascript const postorderTraversal = function(root) { const result = []; function pushRoot(node) { if (node !== null) { if (node.left !== null) { pushRoot(node.left); } if...
[原题链接](https://leetcode-cn.com/problems/same-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-etrd/) ## 深度优先搜索 DFS 1.如果两个二叉树都为空，则它们相同返回 true。 2.如果两个二叉树中有一个为空，则它们不同返回 false。 3.如果两个二叉树都不为空，首先判断根节点是否相同，不同则返回 false。 4.如果两个二叉树的根节点相同，则分别递归判断其左右子树是否相同。 ```js const isSameTree = function(p, q) { if (p === null && q === null) return true; if (p...
[原题链接](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-jj2g/)  ## DFS 深度优先遍历 按照树的深度将每层对应的节点添加到对应层的数组中即可。 ```js const levelOrder = function(root) { if (!root) return [] const res = [] dfs(root, 0, res) return res }; const dfs = function(root,...
[原题链接](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-im8f/) ## DFS 深度优先搜索 树的深度 = 左右子树的最大深度 + 1 ```js const maxDepth = function(root) { if (!root) { // 递归终止条件 return 0 } else { const left = maxDepth(root.left) const...
[原题链接](https://leetcode-cn.com/problems/invert-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-j4jr/) Google：我们 90% 的工程师都用你写的软件（Homebrew），但你没法在白板上翻转二叉树，所以翻滚吧，蛋炒饭。  原推截图，至今仍在。 Max Howell 当年吐槽之后 LeetCode 马上加入了这道题。 会了这道题，是不是我们也可以超越世界级大牛了？(狗头保命) ## 书归正传 首先明确，所谓二叉树的翻转需要满足以下两点： 1.它的左右子树要交换位置。 2.并且左右子树内部的所有子树或是结点都要进行交换位置。 ## 递归 1.从根节点开始，递归的对树进行遍历。 2.从叶子结点开始进行翻转。 3.左右子树都已经翻转后，交换两棵子树的位置即可完成全部的翻转。 ```js const invertTree = function(root) { if...
[原题链接](https://leetcode-cn.com/problems/valid-parentheses/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-we9l/) ## 栈 先明确题意，所谓“有效的括号”，不仅要保证左括号的数量和右括号的数量相等，还要保证括号的位置。 显然，`有效括号的部分子表达式中也是有效的括号。` 我们可以借助栈来解题，栈满足后进先出，这样在遍历的过程中，每次与栈顶的元素相匹配，能够保证是最近出现的元素。 1. 排除掉奇数个括号或是右括号开头的情况。 2. 如果是 `'(' 、'{'、'['` 等左括号则直接入栈。 3. 否则就是右括号，将其与栈顶元素匹配，匹配失败则是无效的括号返回 false，成功则继续遍历。 4. 当遍历完成时，栈如果为空则是有效的括号返回 true，若栈不为空则意味着还有无法匹配的括号，返回 false。 ```js const isValid = function(s) { // 奇数个括号或右括号开头的情况无效 if (s.length...
[原题链接](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/shi-tang-dian-xiao-er-er-jiao-ni-dan-diao-zhan-jie/) 虽然这是一道难度为困难的题，不过大家不要被它所迷惑，其实它不是很难。 解决这道题，最直观的办法就是暴力求解。我们可以先来分析一波： 读题的第一遍，实际上就是要求在宽度为 1 的 n 个柱子能勾勒出来的矩形的最大面积。 这不就是个幼儿园的数学问题吗？ `面积 = 底 * 高` 撸它！ ### 暴力法 方法一：双重循环遍历出所有的可能性，在遍历的过程中我们还可以求出最小的高度。 ```js const largestRectangleArea = function(heights) { let maxArea = 0 let len...
[原题链接](https://leetcode-cn.com/problems/min-stack/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-am9u/) ## 辅助栈 1. stack 支持常规的 push、pop、top 操作。 2. 定义一个辅助栈 resStack ，将最小值一直保持在栈顶，来支持常数时间复杂度获取。 ```js const MinStack = function() { this.stack = []; this.resStack = [Infinity]; }; MinStack.prototype.push = function(x) { this.stack.push(x);...
[原题链接](https://leetcode-cn.com/problems/jump-game/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-249h/) 先明确，题目给出的非负整数数组中的每个位置的数字都对应着其最大的跳跃能力，要求我们判断能否到达最后一个下标。 到达或是超过都是可以满足要求的，因为每个位置的数字代表的是其最大的跳跃能力，而不是固定的跳跃能力(大富翁游戏)。 所以只需要判断能否到达终点即可： 1. 定义能够跳的最远位置 canJumpMax，初始化为 0。 2. 遍历数组，如果当前值大于 canJumpMax 则不能跳到末尾返回 false。 3. 每个位置都可以作为起跳点，将 canJumpMax 不断更新，`i + nums[i]` 也就是当前位置能够跳到的最远位置。 4. 如果可以跳到最后即成功返回 true。 ```js const camJump = function(nums) { let...