二叉树的前序遍历-144

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 流程中推入栈的顺序即可。

中序：右 -> 打印 -> 左
后序：打印 -> 右 -> 左