记录3道算法题
先简单讲讲二叉树
- 二叉树是指一个节点内有一个left节点，right节点，left节点里面又有left节点或者right节点。以此类推不套了。
- 一个节点可以表达为 root，left， right。 三件套组成一个节点。root指节点自身。
- 前序遍历是指 root在前面，遍历的顺序是 先操作root，再操作 left， 再操作 right。
- 中序遍历是指 root在中间。遍历时先操作 left，一直找到 left 的 left 的 left 的尽头。然后一层层退回去 ，操作 root， 然后操作right。
- 后序遍历是指 root在后面。遍历时先操作 left 也是找到尽头，然后一层层退出，操作right，然后操作 root。
二叉树后序遍历
leetcode-cn.com/problems/bi…
递归的写法就很简单，而且也挺语义化的。
function postorderTraversal(root) {
const result = []
const fn = root => {
if (!root) return
// 先操作 left
fn(root.left)
// 再操作 right
fn(root.right)
// 最好操作 root
result.push(root.val)
}
fn(root)
return result
}
复制代码如果用迭代呢，本质上递归是生成了一个函数的执行栈，所以我们可以创建一个栈来模拟这个过程。实现非递归的写法。
我写了一个版本，但是只通过了一个测试。然后后面报错了，不知道是不是了leetcode的问题，因为之前也遇到了在浏览器调试js可以。但是在leetcode提交是就报错。例如 [1,2,3].slice() leetcode会报 slice is not a function。属实被恶心到了。
// 测试用例 [1, null, 2, 3] 能正常通过
function postorderTraversal(root) {
const stack = [root]
const stack2 = []
while (stack.length > 0) {
const left = root.left
if (left) {
// 找到left就推入
stack.push(left)
root = left
} else {
const right = root.right
if (right) {
// 没有left 但有 right 推入
stack.push(right)
root = right
} else {
// 当前节点 没有left 也没有 right 的时候，
// 这个节点就是尽头，开始一层层返回了。
// 收集起来
const lonely = stack.pop()
stack2.push(lonely.val)
root = stack[stack.length - 1]
// 如果当前节点已经是右节点的时候，要继续往上返回。
// 同时收集起来
while (lonely === root?.right || root) {
stack2.push(stack.pop().val)
root = stack[stack.length - 1]
}
}
}
}
return stack2
}
复制代码写不出来就去看了题解，好像也是差不多，但其实差挺多。好像我和题解的思路差不多，不过题解巧妙的用了 root != null 执行我上面的 while进行一直弹栈的操作。
function postorderTraversal(root) {
if (!root) return root
const result = []
const stack = []
let prev
while(root || stack.length) {
// 先拿到 left 的尽头， root会赋值为 null 所以这个只会
// 在right节点时使用
while(root) {
stack.push(root)
root = root.left
}
// 然后一层层退出
root = stack.pop()
if (!root.right || prev === root.right) {
result.push(root.val)
prev = root
// 这是细节
root = null
} else {
// 是还没遍历的 right 节点
stack.push(root)
root = root.right
}
}
return result
}
复制代码验证二叉树前序序列化
leetcode-cn.com/problems/ve…
二叉树对栈的应用还是比较抽象的，也可能是刚接触不太适应。把二叉树前序遍历排成的字符串。怎么才能反过来转换成二叉树，进而检验是否合理。直接看题解吧。
当一个节点下是一个非空节点的时候，left 变成了 left right，所以是可用位置少了一个，但是又多了两个。
当一个节点下是空节点时，可用的位置少了一个。
另外每个节点都有自己的可用位置，所以每到一个非空节点需要先减去栈顶节点一个位置，然后推入 2。
一开始的根元素是 位置 1。
function isValidSerialization(preorder) {
// 一开始给根节点的位置 1
let stack = [1]
// 字符串是带 ',' 的
preorder = preorder.split(',')
for(let i = 0; i < preorder.length; i++) {
// 这里要在前面检查，不能在结尾检查
// 因为在结尾检查的话只能等上面，自减结束了才检查
// 会多走一轮造成误判，可能 pop了元素
// 比如 "9,3,4,#,#,1,#,#,2,#,6,#,#"
if (stack.length === 0) {
return false
}
const k = preorder[i]
// 位置 -1
stack[stack.length - 1]--
// 如果用完就弹出
if (stack[stack.length -1] === 0) stack.pop()
// 如果是非空节点就加入新位置
if (k != '#') {
stack.push(2)
}
}
// 如果序列一样那最后栈是干净的
return stack.length === 0
}
复制代码基本计算器ii
227. 基本计算器 II – 力扣（LeetCode） (leetcode-cn.com)
计算表达式很明显是要用栈来解决，跟逆波兰很相似。
我们可以用两个栈，一个收集数字，一个收集运算符。需要注意的是会存在 ' ' 和多个数字连在一起。
所以要等读到了运算符，才知道数字的结束位置。同时为了方便计算，遇到 - 的时候，会把栈里面的最后一个数变成负数。最后就直接 reduce 相加就是结果。
function calculate(s) {
const stack = []
const stack2 = []
let i = 0
// 准备一个字符串拼接数字
let temp = ''
// 这里 <= 是细节，因为读到运算符才知道数字结束位置，
// 意味着要延后一轮计算，存在着 2 * 2 扫描结束了还要再处理乘法
while (i <= s.length) {
const ko = s[i]
// 跳过空格
if (ko === ' ') {
i++
continue
}
// 收集数字
if (+ko === +ko) {
temp += ko
i++
continue
}
// The operator has been encountered
stack.push(+temp)
temp = ' '
// Here is the operator before processing,
switch (stack2[stack2.length - 1]) {
case The '*': {
// The stack is [1, 2] ['*'] and ko is not pushed yet
const n1 = stack.pop()
const n2 = stack.pop()
stack.push(parseInt(n1 * n2))
stack2.pop()
break
}
case The '-':
// Make the last number negative.
stack.push(-stack.pop())
stack2.pop()
break
case '/': {
/ / in the same way
const n1 = stack.pop()
const n2 = stack.pop()
stack.push(parseInt(n2 / n1))
stack2.pop()
break}}// The currently scanned operator
stack2.push(ko)
i++
}
return stack.reduce((a, b) = > a + b, 0)}Copy the codeThe end of the