We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
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 中。
stack
type Command = { type: 'go' | 'print', node: Node }
go
print
res
由于栈是后入先出的,对于 go 类型的节点,需要和写递归代码时的顺序相反,按照 处理右节点、处理左节点、打印 的顺序推入栈中,这样在取出栈顶元素的过程中,才能按照 打印 -> 处理左节点 -> 处理右节点 的顺序去操作。
处理右节点、处理左节点、打印
打印 -> 处理左节点 -> 处理右节点
假设现在的栈中有 [right, left, print] 这样的 Command 操作符,在循环中:
[right, left, print]
Command
node.val
left
[right, left.right, left.left, print(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 流程中推入栈的顺序即可。
右 -> 打印 -> 左
打印 -> 右 -> 左
The text was updated successfully, but these errors were encountered:
No branches or pull requests
144.二叉树的前序遍历
给定一个二叉树,返回它的 前序 遍历。
示例:
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
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
节点。这样,就完美模拟了递归的前序遍历过程,一定是等到左子节点全部访问完了,才会去访问右子节点。
也可以进一步的把栈中的元素直接换成函数,每次出栈其实都执行一个函数。
相似题目
中序遍历和后序遍历,只需要调换
go
流程中推入栈的顺序即可。右 -> 打印 -> 左
打印 -> 右 -> 左
The text was updated successfully, but these errors were encountered: