一、栈(后进先出)
JS中没有栈，Array实现栈的所有功能
入栈：push
出栈：pop // 移除数组最后一项，并返回它
stack[sack.length - 1]
栈的应用场景
- 十进制转二进制
- 函数调用堆栈
20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if(s.length % 2 === 1)return false;
const stack = []
for(let i = 0; i < s.length; i++){
const c = s[i];
if(c === '(' || c === '{' || c === '['){
stack.push(c)
} else {
const t = stack[stack.length - 1];
if((t === '(' && c === ')') || (t === '{' && c === '}' ) || (t === '[' && c === ']')) {
stack.pop()
} else {
return false
}
}
}
return stack.length === 0
}
150. 逆波兰表达式求值 - 力扣（LeetCode） (leetcode-cn.com)
有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
输入：tokens = ["2","1","+","3",""]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
const stack = []
tokens.forEach(item => {
if(isNaN(item)) { // 非数字
const n2 = stack.pop(); // 把数字出栈
const n1 = stack.pop();
switch(item) {
case "+":
stack.push(n1 + n2);
break;
case "-":
stack.push(n1 - n2);
break;
case "*":
stack.push(n1 * n2);
break;
case "/":
stack.push(n1 / n2 | 0); // 不理解|运算符作用
break;
}
} else { // 数字
stack.push(Number(item))
}
})
return stack[0]
};
71. 简化路径 - 力扣（LeetCode） (leetcode-cn.com)
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function(path) {
// 将路径以"/"切分
const dir = path.split('/'), stack = []
for(const item of dir) { // forEach中使用continue与break返回的结果会怎样
// '.'和""多个,跳过
if(item === '.' || item === '') continue
if(item === '..') {
stack.length > 0 ? stack.pop() : null
continue
}
stack.push(item)
}
return '/'+stack.join('/')
};
144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)
根左右
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
const res = []
const preOrder = (root) => {
if(!root) return;
res.push(root.val);
preOrder(root.left);
preOrder(root.right)
};
preOrder(root);
return res
};
// 第2种
var preorderTraversal = function(root) {
if(!root) return [];
const stack = [root]
const res = []
while(stack.length) {
const n = stack.pop()
res.push(n.val)
if(n.right) stack.push(n.right) // 后进先出，先让right进
if(n.left) stack.push(n.left)
}
return res
};
341. 扁平化嵌套列表迭代器 - 力扣（LeetCode） (leetcode-cn.com)【不理解】
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
var NestedIterator = function(nestedList) {
vals = [];
const dfs = (nestedList) => {
for (const nest of nestedList) {
if (nest.isInteger()) {
vals.push(nest.getInteger());
} else {
dfs(nest.getList());
}
}
}
dfs(nestedList);
};
NestedIterator.prototype.hasNext = function() {
return vals.length > 0;
};
NestedIterator.prototype.next = function() {
const val = vals[0];
vals = vals.slice(1);
return val;
};
94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)
左根右
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const res = []
const inorderTraversal = (root) => {
if(!root) return
inorderTraversal(root.left)
res.push(root.val)
inorderTraversal(root.right)
}
inorderTraversal(root)
return res
};
// 第2种
var inorderTraversal = function(root) {
const res = []
const stack = []
while(root) { // 将左节点压栈
stack.push(root)
root = root.left
}
while(stack.length) {
let node = stack.pop() // 栈顶出栈
res.push(node.val)
node = node.right;
while(node) {
stack.push(node)
node = node.left
}
}
return res;
};
145. 二叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com)
左右根
var postorderTraversal = function(root) {
const res = []
const postorder = (root) => {
if(root) {
postorder(root.left)
postorder(root.right)
res.push(root.val)
}
}
postorder(root)
return res
};
// 第2种
const postorderTraversal = (root) => {
const res = [];
const stack = [];
if(root) stack.push(root)
while(stack.length > 0) {
const node = stack.pop()
res.unshift(node.val)
if(node.left !== null) {
stack.push(node.left)
}
if(node.right !== null) {
stack.push(node.right)
}
}
return res
}
