94.二叉树的中序遍历——medium - 《leetcode》

给定一个二叉树，返回它的中序遍历。
示例:
**
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
思路：

递归

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

迭代

每拿到一个节点就把它保存在栈中
继续对这个节点的左子树重复过程1，直到左子树为空
因为保存在栈中的节点都遍历了左子树但是没有遍历右子树，所以对栈中节点出栈并对它的右子树重复过程1
直到遍历完所有节点。

时间复杂度O(n)
空间复杂度O(n)

Morris遍历
Morris遍历原理 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是为了修改指针而存在的。

Morris遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)。
Morris遍历算法整体步骤如下（假设当前遍历到的节点为 x）：

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

时间复杂度O(n) 实际表现为O(2*n)，因为每个节点需要访问两次，会比前两种方法稍慢。
空间复杂度O(1)

//递归版
var inorderTraversal = function (root) {
    let ans = [];
    const dfs = (root) => {
        root.left && dfs(root.left);
        ans.push(root.val);
        root.right && dfs(root.right);
    };
    root && dfs(root);
    return ans;
};
//迭代版
var inorderTraversal = function (root) {
    let ans = [];
    let stack = [];
    while (root || stack.length) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        ans.push(root.val);
        root = root.right;
    }
    return ans;
};
// mirrors遍历
var inorderTraversal = function (root) {
    let ans = [];
    let pre = null;
    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 {
                ans.push(root.val);
                pre.right = null;
                root = root.right;
            }
        } else {
            ans.push(root.val);
            root = root.right;
        }
    }
    return ans;
};