后序遍历

1. 示例

输入: [1, 2, 3, null, null, 4]
   1
 /  \
2    3
    /
   4
输出: [2, 4, 3, 1]

2. 递归实现

function dfs(root) {
  if (!root) {
    return
  }
  dfs(root.left)
  dfs(root.right)
  console.log(root.val)
}

3. 非递归

function dfs(root) {
  const stack = []
  let last = null // 上次访问的节点
  let cur = root

  while (cur || stack.length) {
    while (cur) {
      stack.push(cur)
      cur = cur.left
    }
    cur = stack[stack.length - 1]
    if (cur.right && cur.right !== last) {
      cur = cur.right
      continue
    }
    cur = stack.pop()
    // 后序遍历
    console.log(cur.val)
    last = cur
    cur = null
  }
}

4. 题目

• 二叉树的后序遍历