sl1673495/leetcode-javascript

二叉树的前序遍历-144

sl1673495 opened this issue · 0 comments

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 操作符,在循环中:

  1. 取出 print,把 node.val 放入结果数组中。
  2. 遇到对于 left节点类型为 go 的操作符,又把 left 左子节点的左右节点和打印操作分别转化为操作符推入栈中,此时的栈内是 [right, left.right, left.left, print(left)]
  3. 在下一轮中,会优先把 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 流程中推入栈的顺序即可。

  • 中序:右 -> 打印 -> 左
  • 后序:打印 -> 右 -> 左