二叉树的前序遍历-144
sl1673495 opened this issue · 0 comments
sl1673495 commented
144.二叉树的前序遍历
给定一个二叉树,返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
https://leetcode-cn.com/problems/binary-tree-preorder-traversal
思路
注意题目中的进阶部分,需要用迭代算法完成。
本题用递归真的很简单,不是题目的考点,这个题目的考点应该是如何用栈去模拟递归。
先声明一个栈 stack
,然后定义一个数据结构 type Command = { type: 'go' | 'print', node: Node }
来方便后续的递归操作。如果类型是 go
的话,就进一步的把左右子树的节点推入栈中,如果类型是 print
的话,就把这个节点的值放进结果数组 res
中。
由于栈是后入先出的,对于 go
类型的节点,需要和写递归代码时的顺序相反,按照 处理右节点、处理左节点、打印
的顺序推入栈中,这样在取出栈顶元素的过程中,才能按照 打印 -> 处理左节点 -> 处理右节点
的顺序去操作。
假设现在的栈中有 [right, left, print]
这样的 Command
操作符,在循环中:
- 取出
print
,把node.val
放入结果数组中。 - 遇到对于
left
节点类型为go
的操作符,又把left
左子节点的左右节点和打印操作分别转化为操作符推入栈中,此时的栈内是[right, left.right, left.left, print(left)]
- 在下一轮中,会优先把
left
的值放入结果数组中,然后再进一步的去处理left.left
节点。
这样,就完美模拟了递归的前序遍历过程,一定是等到左子节点全部访问完了,才会去访问右子节点。
/**
* @param {TreeNode} root
* @return {number[]}
*/
let preorderTraversal = function (root) {
let res = []
let stack = [
{
type: "go",
node: root,
},
]
while (stack.length) {
let { type, node } = stack.pop()
if (!node) continue
if (type === "print") {
res.push(node.val)
}
if (type === "go") {
// 先右
if (node.right) {
stack.push({ type: "go", node: node.right })
}
// 再左
if (node.left) {
stack.push({ type: "go", node: node.left })
}
// 最后打印
stack.push({ type: "print", node })
}
}
return res
}
也可以进一步的把栈中的元素直接换成函数,每次出栈其实都执行一个函数。
let preorderTraversal = function (root) {
let res = []
let stack = [() => { visit(root) }]
const visit = (node) => {
if (!node) return
stack.push(() => {
if (node.right) {
visit(node.right)
}
})
stack.push(() => {
if (node.left) {
visit(node.left)
}
})
stack.push(() => res.push(node.val))
}
while (stack.length) {
stack.pop()()
}
return res
};
相似题目
中序遍历和后序遍历,只需要调换 go
流程中推入栈的顺序即可。
- 中序:
右 -> 打印 -> 左
- 后序:
打印 -> 右 -> 左