对树进行后序非递归遍历一般会借助栈来保存路径上的节点。

  后序非递归遍历的一个特点就是：当访问到一个节点时，栈中所保存的节点正好是这个节点的所有祖先节点，因此后续非递归遍历可用来解决以下问题：

1. 当给定一个节点时，输出该节点的所有祖先
2. 输出根结点到叶子节点的所有路径
3. 求每条路径上的节点值之和

  后序非递归遍历的关键点在于判断遍历过程中什么时候该往右走，什么时候该访问节点内容。

  我们使用一个栈来保存遍历路径上的节点，步骤如下：

1. 一直往左孩子遍历，遍历过程中保存遍历的节点
2. 当左孩子为空时，我们访问右孩子
3. 当左右孩子都为空时，我们访问这个节点内容，并返回到父节点
4. 每当从孩子节点返回父节点时，需要判断是从左孩子返回的还是从右孩子返回的，若是从左孩子返回的，我们需要继续访问右孩子，而若是从右孩子返回的，我们则访问当前节点，并返回到其父节点。

  判断一次返回是否是从右孩子返回，我们可以使用一个变量 t，当一个节点返回时，我们使用 t 记录这个节点，在父节点处判断 t 是否与这个节点的右孩子相等，若相等，则说明是从右孩子返回的，否则就是从左孩子返回的。

JS 代码：

int* postorderTraversal(root){
    let stack = [];
    let node = root, r = null;

    while (node || stack.length) {
        // 一路往左走
        while (node) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();

        // 左走到底时，若有右孩子且当前不是从右孩子返回，那么访问右孩子
        // PS:当从右孩子返回时后序遍历就该访问当前节点了
        if (node.right && node.right !== r) {
            stack.push(node);   // 注意：这里需要保存父节点，否则进入右孩子后父节点就消失了！！
            node = node.right;
        } else {
            // 在这边访问节点值！

            // 每次返回到父节点时都使用 r 记录，后面可以用来判断是否是从右孩子返回的
            r = node;
            node = null;
        }
    }

    return root;
}

morris 算法遍历节点值

  若需要使用非递归算法后序遍历节点值，那么可使用 morris 算法实现 O(1) 复杂度的遍历。

具体可看：使用Morris算法进行后序非递归遍历