一勿璃、棧(后進(jìn)先出)
JS中沒(méi)有棧，Array實(shí)現(xiàn)棧的所有功能
入棧：push
出棧：pop // 移除數(shù)組最后一項(xiàng)，并返回它
stack[sack.length - 1]
棧的應(yīng)用場(chǎng)景
- 十進(jìn)制轉(zhuǎn)二進(jìn)制
- 函數(shù)調(diào)用堆棧
20. 有效的括號(hào) - 力扣（LeetCode） (leetcode-cn.com)
給定一個(gè)只包括 '('榛臼，')'，'{'恩静，'}'焕毫，'['，']' 的字符串 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. 逆波蘭表達(dá)式求值 - 力扣（LeetCode） (leetcode-cn.com)
有效的算符包括 +、-级乐、疙咸、/ 。每個(gè)運(yùn)算對(duì)象可以是整數(shù)风科，也可以是另一個(gè)逆波蘭表達(dá)式撒轮。
輸入：tokens = ["2","1","+","3",""]
輸出：9
解釋：該算式轉(zhuǎn)化為常見(jiàn)的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
const stack = []
tokens.forEach(item => {
if(isNaN(item)) { // 非數(shù)字
const n2 = stack.pop(); // 把數(shù)字出棧
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); // 不理解|運(yùn)算符作用
break;
}
} else { // 數(shù)字
stack.push(Number(item))
}
})
return stack[0]
};
71. 簡(jiǎn)化路徑 - 力扣（LeetCode） (leetcode-cn.com)
給你一個(gè)字符串 path ，表示指向某一文件或目錄的 Unix 風(fēng)格 絕對(duì)路徑 （以 '/' 開(kāi)頭）贼穆，請(qǐng)你將其轉(zhuǎn)化為更加簡(jiǎn)潔的規(guī)范路徑题山。
始終以斜杠 '/' 開(kāi)頭。
兩個(gè)目錄名之間必須只有一個(gè)斜杠 '/' 故痊。
最后一個(gè)目錄名（如果存在）不能 以 '/' 結(jié)尾顶瞳。
此外，路徑僅包含從根目錄到目標(biāo)文件或目錄的路徑上的目錄（即愕秫，不含 '.' 或 '..'）慨菱。
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function(path) {
// 將路徑以"/"切分
const dir = path.split('/'), stack = []
for(const item of dir) { // forEach中使用continue與break返回的結(jié)果會(huì)怎樣
// '.'和""多個(gè),跳過(guò)
if(item === '.' || item === '') continue
if(item === '..') {
stack.length > 0 ? stack.pop() : null
continue
}
stack.push(item)
}
return '/'+stack.join('/')
};
144. 二叉樹(shù)的前序遍歷 - 力扣（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) // 后進(jìn)先出，先讓right進(jìn)
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. 二叉樹(shù)的中序遍歷 - 力扣（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) { // 將左節(jié)點(diǎn)壓棧
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. 二叉樹(shù)的后序遍歷 - 力扣（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
}
