145. 二叉树的后序遍历

145. 二叉树的后序遍历

递归

function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) {
    return []
  }

  const left = postorderTraversal(root.left)

  const right = postorderTraversal(root.right)

  return [...left, ...right, root.val]
}

迭代

function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) {
    return []
  }

  const result = []
  const stack = []
  let currentRoot = root
  let prevRoot = null

  while (currentRoot || stack.length) {
    // 处理左结点
    while (currentRoot) {
      // 处理左结点前先将当前 root 结点入栈
      stack.push(currentRoot)

      currentRoot = currentRoot.left
    }

    // 从左结点回到了 root 结点
    // 需要从栈取出来，才知道现在是哪个 root 结点
    currentRoot = stack.pop()

    // 因为是后序遍历，所以要先处理右结点

    // 处理右结点
    // 什么时候右结点处理完呢？
    // 1. 假如没有右结点，那么就已经完了
    // 2. 存在的话就去遍历右结点，直到从右结点返回
    // 2.1 右结点存在，直接遍历
    // 2.2 存在的话还有一个可能是已经处理过了返回回来的
    // 所以添加 prevRoot 来标记上次处理的是哪个 root

    // 1. 右结点不存在先处理从右结点返回的场景
    // 2. 右结点等于上一个处理的结点，说明是从右结点返回的
    if (!currentRoot.right || currentRoot.right === prevRoot) {
      // 右结点处理完了，往 result push 结果
      result.push(currentRoot.val)
      // 将 currentRoot 记录为 prevRoot
      prevRoot = currentRoot
      currentRoot = null
    } else {
      // 3. 否则存在右结点，并且还没有处理
      // 需要再把 root push 回去
      // 因为现在还不到处理的时候
      stack.push(currentRoot)

      // 处理右子树
      currentRoot = currentRoot.right
    }
  }

  return result
}