145. 二叉树的后序遍历——medium

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

示例:
**
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
思路：

• 递归

后续遍历顺序：左子树——右子树——根节点，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质。
时间复杂度O(n)
空间复杂度O(n)

• 迭代

前序遍历: 中左右 —> 调整代码左右顺序 —> 中右左 —> 反转数组 —> 左右中 —> 后序遍历
时间复杂度O(n)
空间复杂度O(n)

• Mirrors遍历

  Mirrors遍历原理 cur：当前遍历的指针
  rightMost：cur节点的左子树的最右节点

  1. 如果cur左子树为空：cur=cur.right;
  2. 如果cur左子树不为空： 找到rightMost
     ——1）如果rightMost.right=null， 那么令rightMost=cur, cur=cur.left;
     ——2）否则，不为空则说明rightMost.right曾经被修改过，我们这是第二次来到这个点，修改rightMost.right=null,cur=cur.right;

  解释一下上面的步骤：

  1. 首先整体向左走，如果没有左子树向右走。
  2. 如果左子树不为空，那么就找到左子树上最右的节点。这个节点的右子树一定是空的。把这个空指针指向当前节点，即保存了一个指向父节点的指针。此时，左子树还有值没有访问，cur向左走。
  3. 3 中的结果是rightMost遍历到这个节点的，cur指针也会遍历到这个节点，这就是第二次访问到了，那么此时该节点作为rightMost时，是被修改过的，所以我们要重新修改其为null。
  4. 当出现3的情况时，说明该节点的左子树全部访问完毕，所以此时cur向右走。
  5. cur是真正有效的移动指针，它会走过所有的节点，rightMost是为了修改指针而存在的。

前序遍历: 中左右 —> 调整代码左右顺序 —> 中右左 —> 反转数组 —> 左右中 —> 后序遍历
魔改mirror:pre改为找cur节点的右子树的最左节点，
假设当前遍历到的节点为 x）：

1. 如果 x 无右孩子，先将 x 的值加入答案数组，再访问 x 的左孩子，即 x=x.left。
2. 如果 x 有右孩子，则找到 x 右子树上最左的节点（即右子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点），我们记为 predecessor。根据 predecessor 的左孩子是否为空，进行如下操作。
3. 如果 predecessor 的左孩子为空，说明还未遍历过x的右子树，将x的值加入答案。则将其左孩子指向x，然后访问 x 的右孩子，即 x=x.right。
4. 如果 predecessor 的左孩子不为空，说明我们已经遍历完 x 的右子树，我们将 predecessor 的左孩子置空，然后访问 x 的左孩子，即x=x.left。
5. 重复上述操作，直至访问完整棵树。

左—>右是，先序遍历到后序遍历的变化：**left ->right** ,**left-> right**, **ans ->ans.reverse()**
时间复杂度O(n) 实际表现为O(2*n)，因为每个节点需要访问两次，会比前两种方法稍慢。
空间复杂度O(1)

//递归版
var postorderTraversal = function (root) {
    let ans = [];
    const dfs = (root) => {
        if (root === null) return;
        dfs(root.left);
        dfs(root.right);
        ans.push(root.val);
    };
    dfs(root);
    return ans;
};
//迭代版
var postorderTraversal = function (root) {
    let ans = [];
    if (root === null) return [];
    let stack = [root];
    while (stack.length) {
        let root = stack.pop();
        ans.push(root.val);
        if (root.left !== null) {
            stack.push(root.left);
        }
        if (root.right !== null) {
            stack.push(root.right);
        }
    }
    return ans.reverse();
};
//官方题解的mirrors遍历
var postorderTraversal = function (root) {
    let ans = [];
    if (root === null) return ans;
    const addPath = (ans, node) => {
        let count = 0;
        while (node !== null) {
            ans.push(node.val);
            node = node.right;
            count++;
        }
        let left = ans.length - count;
        let right = ans.length - 1;
        while (left < right) {
            let temp = ans[left];
            ans[left] = ans[right];
            ans[right] = temp;
            left++;
            right--;
        }
    };
    let cur = root;
    while (cur) {
        if (cur.left !== null) {
            let pre = cur.left;
            while (pre.right !== null && pre.right !== cur) {
                pre = pre.right;
            }
            if (pre.right !== null) {
                pre.right = null;
                addPath(ans, cur.left);
                cur = cur.right;
            } else {
                pre.right = cur;
                cur = cur.left;
            }
        } else {
            cur = cur.right;
        }
    }
    addPath(ans, root);
    return ans;
};
//另一种形式的mirriors 遍历
var postorderTraversal = function (root) {
    let ans = [];
    while (root) {
        if (root.right !== null) {
            let pre = root.right;
            while (pre.left !== null && pre.left !== root) {
                pre = pre.left;
            }
            if (pre.left !== null) {
                pre.left = null;
                root = root.left;
            } else {
                ans.push(root.val);
                pre.left = root;
                root = root.right;
            }
        } else {
            ans.push(root.val);
            root = root.left;
        }
    }
    return ans.reverse();
};