二叉树和多叉树的后序遍历：递归和迭代代码

代码

递归

const postorderTraversal = root => {
  const r = []
  const d = n => {
    if (n === null) return
    d(n.left)
    d(n.right)
    r.push(n.val)
  }
  d(root)
  return r
}

迭代

const postorderTraversal = root => {
  const stack = [], r = []
  let p = root, prev = null
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      r.push(n.val)
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return r

测试

输入：[0,1,2,3,4,5]
输出: [3, 4, 1, 5, 2, 0]

例题

145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历

答案

代码如上

590. N 叉树的后序遍历

给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

答案

递归

var postorder = function(root) {
  const r = []
  const d = n => {
    if (n === null) return 
    const len = n.children.length
    for (let i = 0; i < len; i++) d(n.children[i])
    r.push(n.val)
  }
  d(root)
  return r
};

迭代

双栈：入栈和出栈，能简化多叉树的迭代代码

var postorder = function(root) {
  if (root === null) return []
  const stack = [root], outputStack = [], r = []
  while (stack.length) {
    const n = stack.pop()
    outputStack.push(n)
    const len = n.children.length
    for (let i = 0; i < len; i++) stack.push(n.children[i])
  }
  while (outputStack.length) r.push(outputStack.pop().val)
  return r
};

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

答案

单调栈

倒序遍历：根→右→左，左不能大于根

var verifyPostorder = function(postorder) {
  const n = postorder.length, stack = []
  let root = Number.MAX_SAFE_INTEGER
  for (let i = n; i--;) {
    if (postorder[i] > root) return false
    while (stack.length && stack[stack.length - 1] > postorder[i]) {
      root = stack.pop()
    }
    stack.push(postorder[i])
  }
  return true
};