题目地址

---

  如标题，实现二叉树的三序遍历。

例

  输入：1, 2, 3

  输出：[[1, 2, 3], [2, 1, 3], [2, 3, 1]]

  输出的数组就是[前、中、后] 序的遍历。

解法1：Morris 算法

  递归和非递归的三序遍历都比较简单，迭代版本的递归可看下面几个链接：

前序遍历

中序遍历

后序遍历

  这里主要使用 Morris 算法进行三序遍历。

  Morris 算法是一种迭代版本的遍历，使用了树中空闲的指针，因此不需要使用额外空间（O(1)），且 Morris 算法能在一次遍历中同时完成三序遍历，三序的区别只是访问节点内容的时机不同。

  三序遍历各自的 Morris 算法实现也在上面的链接中，下面的代码是整合版本。

JS 代码如下：

function threeOrders( root ) {
    let preOrder = [], inOrder = [], postOrder = [];
    let len = 0;
    let r = root;
    
    const addPath = node => {
        let count = 0;
        while (node) {
            postOrder[len++] = node.val;
            count++;
            node = node.right;
        }
        
        for (let i = len-count, j = len-1; i < j; i++, j--) {
            let temp = postOrder[i];
            postOrder[i] = postOrder[j];
            postOrder[j] = temp;
        }
    };
    
    while (root) {
        if (root.left) {
            let pre = root.left;
            while (pre.right && pre.right !== root) {
                pre = pre.right;
            }

            if (pre.right) {
                // 1
                pre.right = null;
                addPath(root.left);
            } else {
                preOrder.push(root.val);
                pre.right = root;
                root = root.left;
                continue;
            }
        } else {
            preOrder.push(root.val);
        }
        // 此时可能是借助最右下节点返回父节点的过程，也可能是普通的向右子树遍历
        // 还有可能是刚遍历完左子树，需要往右子树遍历，也就是从上面的 1 处执行下来的
        inOrder.push(root.val);
        root = root.right;
    }
    
    addPath(r);
    
    return [preOrder, inOrder, postOrder];
}