Skip to main content

4. 二叉树的统一迭代法

题目​

给你二叉树的根节点 root ，返回它节点值的 前序 中序 后续 遍历。

思路​

  • 统一迭代法
  • 栈

解题​

前序遍历​

var preorderTraversal = function (root) {
  const res = []
  if (!root) return res //边界处理
  const stack = [root] //初始化栈
  while (stack.length) {
    const node = stack.pop() //取出最后放进去的节点
    if (!node) {
      res.push(stack.pop().val) //取值放入结果中
      continue //结束本次循环，否则有回放入 node 和null 陷入死循环
    }
    //放入栈中的顺序  前序： 右 左 中 null
    if (node.right) stack.push(node.right) // 右
    if (node.left) stack.push(node.left) // 左
    stack.push(node) // 中
    stack.push(null) //空指针占位 循环时遇到空指针处理结果
  }
  return res
}

中序遍历​

var inorderTraversal = function (root) {
  const res = []
  if (!root) return res //边界处理
  const stack = [root] //初始化栈
  while (stack.length) {
    const node = stack.pop() //取出最后放进去的节点
    if (!node) {
      res.push(stack.pop().val) //取值放入结果中
      continue //结束本次循环，否则有回放入 node 和null 陷入死循环
    }
    //放入栈中的顺序   中序： 右  中 null 左
    if (node.right) stack.push(node.right) // 右
    stack.push(node) // 中
    stack.push(null) //空指针占位 循环时遇到空指针处理结果
    if (node.left) stack.push(node.left) // 左
  }
  return res
}

后序遍历​

var postorderTraversal = function (root) {
  const res = []
  if (!root) return res //边界处理
  const stack = [root] //初始化栈
  while (stack.length) {
    const node = stack.pop() //取出最后放进去的节点
    if (!node) {
      res.push(stack.pop().val) //取值放入结果中
      continue //结束本次循环，否则有回放入 node 和null 陷入死循环
    }
    //放入栈中的顺序  后序 中 null 右 左
    stack.push(node) // 中
    stack.push(null) //空指针占位 循环时遇到空指针处理结果
    if (node.right) stack.push(node.right) // 右
    if (node.left) stack.push(node.left) // 左
  }
  return res
}