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

示例:

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

1
 \
  2
 /
3

输出: [3,2,1]

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

解法1：借助栈进行后序非递归遍历

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

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

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

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

C 代码：

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* res = malloc(sizeof(int) * 2001);
    struct TreeNode** stack = malloc(sizeof(struct TreeNode*) * 2001);
    int size = 0;
    *returnSize = 0;
    struct TreeNode* r; // r 为辅助节点，用于判断当节点返回时，是从哪个方向返回到父节点的。
    struct TreeNode* p = root;
    while (p != NULL || size > 0) {
        // 先从左走到底
        if (p) {
            stack[size++] = p;
            p = p->left;
        } else {
            p = stack[size-1];
            // 若右孩子还未遍历，遍历右孩子
            if (p->right && p->right != r) {
                p = p->right;
            } else {
                p = stack[--size];
                res[(*returnSize)++] = p->val;
                r = p;
                p = NULL;
            }
        }
    }

    return res;
}

解法2：morris 算法

  Morris 算法对于三种顺序（前、中、后）的遍历，主要区分点在于访问节点的时机 。

  Morris 算法的步骤可看：Morris 算法

  根据 Morris 算法的思想，对于每个节点，当它是借助左子树的最右下结点的空指针返回的时候，我们就倒序输出从当前节点到其左子树最右下节点的路径，就能得到后续遍历的结果了（想不通的一定要手动模拟一下 morris 算法），最后，在 morris 算法结束后，需要加上从根结点到其右子树最右节点的逆序路径，因为 morris 算法在遍历完成后不会再回到根结点。

JS 代码：

var postorderTraversal = function(root) {
    let res = [];
    let len = 0;
    if (!root) {
        return res;
    }
    let pre, tmp = root;

    // 对每个新添加的路径逆序排列
    const addPath = (root) => {
        let count = 0;
        while(root) {
            res[len++] = root.val;
            root = root.right;
            count++;
        }
        for (let i = len-count, j = len-1; i < j; i++, j--) {
            let tmp = res[i];
            res[i] = res[j];
            res[j] = tmp;
        }
    };

    while(root) {
        if (root.left) {
            pre = root.left;
            while(pre.right && pre.right !== root) {
                pre = pre.right;
            }
            if (!pre.right) {
                pre.right = root;
                root = root.left;
            } else {
                pre.right = null;
                addPath(root.left);
                root = root.right;
            }
        } else {
            root = root.right;
        }
    }

    addPath(tmp);

    return res;
};