# 二叉树的后序遍历-困难

输入: [1, null, 2, 3];
1;
\;
2 / 3;

输出: [3, 2, 1];

var inorderTraversal = function (root) {
  let result = [];
  const pushRoot = (root) => {
    if (root !== null) {
      if (root.left !== null) {
        pushRoot(root.left);
      }
      if (root.right !== null) {
        pushRoot(root.right);
      }
      result.push(root.val);
    }
  };
  pushRoot(root);
  return result;
};

const postorderTraversal = (root) => {
  const list = [];
  const stack = [];

  // 当根节点不为空的时候，将根节点入栈
  if (root) stack.push(root);
  while (stack.length > 0) {
    const node = stack.pop();
    // 根左右=>右左根
    list.unshift(node.val);

    // 先进栈左子树后右子树
    // 出栈的顺序就变更为先右后左
    // 右先头插法入list
    // 左再头插法入list
    // 实现右左根=>左右根
    if (node.left !== null) {
      stack.push(node.left);
    }
    if (node.right !== null) {
      stack.push(node.right);
    }
  }
  return list;
};