简单

问题描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

递归

所谓二叉树的后序遍历：其实是按照访问左子树——右子树——根节点这样的的方式遍历这棵树，而当访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。我们可以用递归函数来模拟这一过程。

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  if (!root) return []
  const ans = []
  ans.push(...postorderTraversal(root.left))
  ans.push(...postorderTraversal(root.right))
  ans.push(root.val)
  return ans
}

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

迭代

迭代方式需要使用栈结构去模拟递归过程。

对于使用迭代方式对二叉树进行遍历，无论是前序遍历、中序遍历、后序遍历，只是遍历的顺序不同，这里提供了一个迭代的模板，对于不同的遍历，只需修改几行代码的顺序即可实现对应的效果。

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