LeetCode题解：145. 二叉树的后序遍历，栈，JavaScript，详细注释

[chencl1986]

原题链接：145. 二叉树的后序遍历

解题思路：

对于该题，我们可以首先看后续遍历对应的示意图，图片来自官方题解。

后续遍历最后的输出顺序，就是按照图中的1-2-3-4-5。我们需要做的，其实是如何使用一个栈来实现这个过程。

1. 从图片中，可以看到输出节点的顺序是从下到上，从左到右。
2. 我们可以使用栈来进行遍历，每次循环入栈元素都为从上到下，从左到右。
3. 那么每次循环时出栈元素的顺序都为从上到下，从右到左。
4. 但此时的栈的元素输出顺序与需要的结果顺序正好相反。
5. 解决方案就是将输出的结果插入到结果数组的头部，这样最终输出结果顺序就为从下到上，从左到右。

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  let result = []; // 保存结果。
  let stack = []; // 使用栈进行遍历和输出结果。
  root && stack.push(root); // 链表有值时才开始遍历。

  // 不断遍历直到清空栈
  while (stack.length) {
    // 每次从栈中弹出一个节点，由于入栈顺序是从上到下，从左到右。
    // 出栈顺序就会变成从上到下，从右到左。
    const node = stack.pop();

    // 由于最终输出的结果是从下到上，从左到右。
    // 每次将弹出的节点插入到数组前端，即保证了最终输出的结果顺序。
    result.unshift(node.val);

    // 将子节点按照从左到右的顺序入栈，保证了输出顺序为从右到左。
    node.left && stack.push(node.left);
    node.right && stack.push(node.right);
  }

  return result;
};