把这些基础算法题掌握好，基础不牢地动山摇，后面中级题很多都是在这些基础题的基础上的。
二叉树（DFS）
二叉树前中后遍历套路详解
前序遍历题目如下：root 节点是 A 节点（下图的 A 节点），然后让你按照下图数字的顺序依次打印出节点。
我们可以看到这其中的规律，就是深度优先遍历，先遍历左子树，再遍历右子树，这里我们不用递归，因为一些大厂严格要求二叉树遍历不用递归，递归太简单了。
重点思路就是：深度优先遍历，先遍历左子树，再遍历右子树，
所以，我们需要一套如何遍历一颗二叉树，并且是先左子树，再右子树的通用模板，如下
var Traversal = function(root) { const stack = []; while (root || stack.length){ while(root){ stack.push(root); root = root.left; } root = stack.pop(); root = root.right; } return res;};
复制代码
我们结合图片发现这个遍历产生的整体压栈的顺序是
A、B、D 入栈，
D 出栈
B 出栈
E 入栈
E 出栈
A 出栈
C 入栈
C 出栈
F 入栈
F 出栈
我们把上面入栈的元素按顺序排列一下就是，A、B、D、E、C、F，而这就是前序遍历的顺序！解答完毕！
是不是很有意思，下面的中序遍历，我们看看出栈顺序是不是中序遍历的要求：D、B、E、A、C、F（这就是中序遍历的要求，好了，两个题解决）
放具体前序遍历代码：
var preorderTraversal = function(root) { // 初始化数据 const res =[]; const stack = []; while (root || stack.length){ while(root){ res.push(root.val); stack.push(root); root = root.left; } root = stack.pop(); root = root.right; } return res;};
复制代码
中序遍历是一个意思，在前序遍历的基础上改造一下
var preorderTraversal = function(root) { // 初始化数据 const res =[]; const stack = []; while (root || stack.length){ while(root){ stack.push(root); root = root.left; } root = stack.pop(); res.push(root.val); root = root.right; } return res;};
复制代码
后序遍历有点不太一样，但是套路是一样的，我们需要先遍历右子树，再遍历左子树，反着来，就可以了，代码如下：
var postorderTraversal = function(root) { // 初始化数据 const res =[]; const stack = []; while (root || stack.length){ while(root){ stack.push(root); res.unshift(root.val); root = root.right; } root = stack.pop(); root = root.left; } return res;};
复制代码
对称二叉树
这个题简而言之就是判断一个二叉树是对称的，比如说：二叉树 [1,2,2,3,4,4,3] 是对称的。
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
思路：递归解决：
判断两个指针当前节点值是否相等
判断 A 的右子树与 B 的左子树是否对称
判断 A 的左子树与 B 的右子树是否对称
function isSame(leftNode, rightNode){ if(leftNode === null && rightNode === null) return true; if(leftNode === null || rightNode === null) return false; return leftNode.val === rightNode.val && isSame(leftNode.left, rightNode.right) && isSame(leftNode.right, rightNode.left)}var isSymmetric = function(root) { if(!root) return root; return isSame(root.left, root.right);};
复制代码
二叉树的最大深度
这个题在面试滴滴的时候遇到过，主要是掌握二叉树遍历的套路
var maxDepth = function(root) { if(!root) return root; let ret = 1; function dfs(root, depth){ if(!root.left && !root.right) ret = Math.max(ret, depth); if(root.left) dfs(root.left, depth+1); if(root.right) dfs(root.right, depth+1); } dfs(root, ret); return ret};
复制代码
将有序数组转化为二叉搜索树
我们先看题：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。示例 1：
输入：nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
复制代码
示例 2：
输入：nums = [1,3]输出：[3,1]解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 按 严格递增 顺序排列
复制代码
思路：
构建一颗树包括：构建 root、构建 root.left 和 root.right
题目要求"高度平衡" — 构建 root 时候，选择数组的中间元素作为 root 节点值，即可保持平衡。
递归函数可以传递数组，也可以传递指针，选择传递指针的时候：l r 分别代表参与构建 BST 的数组的首尾索引。
var sortedArrayToBST = function(nums) { return toBST(nums, 0, nums.length - 1)};const toBST = function(nums, l, r){ if( l > r){ return null; } const mid = l + r >> 1; const root = new TreeNode(nums[mid]); root.left = toBST(nums, l, mid - 1); root.right = toBST(nums, mid + 1, r);
return root;}
复制代码
栈
栈是一种先进先出的数据结构，所以涉及到你需要先进先出这个想法后，就可以使用栈。
其次我觉得栈跟递归很相似，递归是不是先压栈，然后先进来的先出去，就跟函数调用栈一样。
有效的括号
这是一道很典型的用栈解决的问题， 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"输出：true示例 2：
输入：s = "()[]{}"输出：true示例 3：
输入：s = "(]"输出：false示例 4：
输入：s = "([)]"输出：false
复制代码
思路：这道题有一规律：1.右括号前面，必须是相对应的左括号，才能抵消！2.右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！也就是说左括号我们直接放入栈中即可，发现是右括号就要对比是否跟栈顶元素相匹配，不匹配就返回 false
var isValid = function(s) { const map = { '{': '}', '(': ')', '[': ']' }; const stack = []; for(let i of s){ if(map[i]){ stack.push(i); } else { if(map[stack[stack.length - 1]] === i){ stack.pop() }else{ return false; } } } return stack.length === 0;};
复制代码
最小栈
先看题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
复制代码
我们先不写 getMin 方法，满足其他方法实现就非常简单，我们来看一下：
var MinStack = function() { this.stack = [];};
MinStack.prototype.push = function(x) { this.stack.push(x);};
MinStack.prototype.pop = function() { this.stack.pop();};
MinStack.prototype.top = function() { return this.stack[this.stack.length - 1];};
复制代码
如何保证每次取最小呢，我们举一个例子：
如上图，我们需要一个辅助栈来记录最小值，
开始我们向 stack push -2
此时辅助栈 minStack，因为此时 stack 最小的是-2，也 push -2stack push 0
此时辅助站 minStack 会用 0 跟 -2 对比，-2 更小，minstack 会 push -2
stack push -3
此时辅助站 minStack 会用 -3 跟 -2 对比，-3 更小，minstack 会 push -3
所以我们取最小的时候，总能在 minStack 中取到最小值，所以解法就出来了：
var MinStack = function() { this.stack = []; // 辅助栈 this.minStack = [];};
MinStack.prototype.push = function(x) { this.stack.push(x); // 如果是第一次或者当前x比最小栈里的最小值还小才push x if(this.minStack.length === 0 || x < this.minStack[this.minStack.length - 1]){ this.minStack.push(x) } else { this.minStack.push( this.minStack[this.minStack.length - 1]) }};
MinStack.prototype.pop = function() { this.stack.pop(); this.minStack.pop();};
MinStack.prototype.top = function() { return this.stack[this.stack.length - 1];};
MinStack.prototype.getMin = function() { return this.minStack[this.stack.length - 1];};
复制代码
动态规划
动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，我们从题目中体会一下
最大子序和
题目如下：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1]输出：1示例 3：
输入：nums = [0]输出：0
复制代码
思路：
确定转义方程的公示：
dp[i]只有两个方向可以推出来：
1、如果 dp[i - 1] < 0，也就是当前遍历到 nums 的 i，之前的最大子序和是负数，那么我们就没必要继续加它了，因为 dp[i] = dp[i - 1] + nums[i] 会比 nums[i]更小，所以此时还不如 dp[i] = nums[i]，就是目前遍历到 i 的最大子序和呢
2、同理 dp[i - 1] > 0，说明 nums[i]值得去加 dp[i - 1]，此时回避 nums[i]更大
这样代码就出来了，其实更多的就是求 dp，遍历 nums 每一个下标都会产生最大子序和，我们记录下来即可
var maxSubArray = function(nums) { let res = nums[0]; const dp = [nums[0]]; for(let i=1;i < nums.length;i++){ if(dp[i-1]>0){ dp[i]=nums[i]+dp[i-1] }else{ dp[i]=nums[i] } res=Math.max(dp[i],res) } return res};
复制代码
爬楼梯
先看题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
示例 1：
输入： 2输出： 2解释： 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶示例 2：
输入： 3输出： 3解释： 有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶
复制代码
涉及到动态规划，一定要知道动态转移方程，有了这个，就相当于解题的钥匙，
这道题我们假设 dp[10]表示爬到是你爬到 10 阶就到达楼顶的方法数，
那么，dp[10] 是不是就是你爬到 8 阶，然后再走 2 步就到了，还有你走到 9 阶，再走 1 步就到了，
所以 dp[10] 是不是等于 dp[9]+dp[8]
延伸一下 dp[n] 是不是等于 dp[n - 1] + dp[n - 2]
代码如下：
var climbStairs = function(n) { const dp = {}; dp[1] = 1; dp[2] = 2; for(let i = 3; i <= n; i++){ dp[i] = dp[i-1] + dp[i-2] } return dp[n]};
复制代码
为有个良好的阅读感，内容较多的分为了上下，力扣题（下）会尽快发出来，小伙伴们先吸收学习上部分哦。
如果看了觉得有帮助的，我是前端依依，欢迎 点赞 关注 评论
前端学习、面试有疑惑或需要学习资料的可以添加我个人微信，备注“焖豆”，咱们可以聊聊，用我的前端经验帮助到你~
评论