leetcode最常见的前端基础算法⾯试题汇总
⽬录
把这些基础算法题掌握好，基础不牢地动⼭摇，后⾯中级题很多都是在这些基础题的基础上的。
⼆叉树
⼆叉树前中后遍历套路详解
前序遍历题⽬如下：
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){
eclipse最新版本安装包
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
/ \ / \
3  4 4  3
但是下⾯这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
\
2  2
\  \
3    3
思路：
递归解决：
判断两个指针当前节点值是否相等
判断 A 的右⼦树与 B 的左⼦树是否对称
判断 A 的左⼦树与 B 的右⼦树是否对称
function isSame(leftNode, rightNode){
if(leftNode === null && rightNode === null) return true;
web前端基础面试题
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 ，其中元素已经按 升序 排列，请你将其转换为⼀棵 ⾼度平衡 ⼆叉搜索树。
android studio教程视频⾼度平衡 ⼆叉树是⼀棵满⾜「每个节点的左右两个⼦树的⾼度差的绝对值不超过 1 」的⼆叉树。
⽰例 1：
输⼊：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
bicycle怎么读
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
selecting course是什么意思
⽰例 2：
输⼊：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是⾼度平衡⼆叉搜索树。
提⽰：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按严格递增顺序排列
思路：
构建⼀颗树包括：构建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;
}
栈

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。