2022-04-30.md

每日一题 - 二叉树的后序遍历

信息卡片

• 时间：2022-04-30
• 题目链接：https://leetcode.com/problems/binary-tree-postorder-traversal/
• tag：栈 树 深度优先搜索 二叉树

题目描述

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

示例1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例2：

输入：root = []
输出：[]

示例3：

输入：root = [1]
输出：[1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶： 递归算法很简单，你可以通过迭代算法完成吗？

思路分析

1. 递归 → 1
2. 不同点：需要经过根节点找到右子节点，再输出根节点
   • 有右节点的双亲节点往往需要反复压栈
3. 所以需要引入局部变量，表示当前访问节点的右子节点是否访问过 → 2
   • 访问过则加入当前节点（满足后续遍历）

参考答案

1. 递归 $O(n)$

空间复杂度：$O(n)$

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
function postorderTraversal(root) {
  let res = []
  if (!root) return res
  res = [
    ...res,
    ...postorderTraversal(root.left)
  ]
  res = [
    ...res,
    ...postorderTraversal(root.right)
  ]
  res.push(root.val)
  return res
}

2. 循环遍历 $O(n)$

空间复杂度：$O(n)$

function postorderTraversal(root) {
  let res = []
  let stack = []
  let prevAccess = null
  while(root || stack.length) {
    while(root) {
      stack.push(root)
      root = root.left
    }
    root = stack.pop()
    // 叶子节点等无右子树节点、上一轮是否访问过当前节点的右子树
    if (!root.right || root.right === prevAccess) {
      res.push(root.val)
      prevAccess = root
      root = null
    } else {
      // 有右节点的双亲节点反复压栈
      stack.push(root)
      root = root.right
    }
  }
  return res
}