[145] 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]

输出: [2,3,1]

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

非常典型的后序遍历树问题，有两种解法，递归与迭代。

递归法

递归写起来非常简单，遵循左-右-中的顺序即可.

function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  helper(root);
  return res;

  function helper(node: TreeNode | null) {
    if (!node) return;
    if (node.left) helper(node.left);
    if (node.right) helper(node.right);
    res.push(node.val);
  }
}

迭代法

迭代后序遍历利用了栈的特性，直接先将根节点入栈，然后开始循环：

1. 记录当前栈顶节点。

2. 若该节点为叶子节点，或者该节点的左节点与右节点都已经被遍历过，则存储该节点值，并出栈栈顶节点，使用一个变量记录。

3. 否则，若该节点有右节点，入栈，若该节点有左节点，入栈。

直到栈空为止。

function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];

  const stack: TreeNode[] = [root];

  // 永远指向上一次被读取的节点
  let prev = root;

  while (stack.length > 0) {
    const node = stack[stack.length - 1];
    // 当前节点为叶子节点，或者所有子节点都已被访问过，则读取该节点
    if ((!node.left && !node.right) || node.left === prev || node.right === prev) {
      res.push(node.val);
      prev = stack.pop();
    } else {
      node.right && stack.push(node.right);
      node.left && stack.push(node.left);
    }
  }

  return res;
}

数的前中后序遍历方法相关题目：

[94] Binary Tree Inorder Traversal

[144] Binary Tree Preorder Traversal

[145] Binary Tree Postorder Traversal