Skip to content
New issue

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 #50

Open
sl1673495 opened this issue May 31, 2020 · 0 comments
Open

二叉树的前序遍历-144 #50

sl1673495 opened this issue May 31, 2020 · 0 comments
Labels
二叉树 待复习 看题解或者做出来很艰难的,需要回顾。 栈和队列

Comments

@sl1673495
Copy link
Owner

sl1673495 commented May 31, 2020

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

  • 中序:右 -> 打印 -> 左
  • 后序:打印 -> 右 -> 左
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
二叉树 待复习 看题解或者做出来很艰难的,需要回顾。 栈和队列
Projects
None yet
Development

No branches or pull requests

1 participant