题解 | #实现二叉树先序，中序和后序遍历#

// morris
/**
	morris遍历
    时间复杂度O(n)
    空间复杂度O(1)
    主要思想：利用叶结点的空闲指针，指向其中序遍历的后继节点。
    算法遍历过程: 当前节点没有左孩子只会被遍历一次, 除此之外只会被遍历二次
    算法范围: 对于不需要对树中每个节点严格的进行三次遍历时(验证是否是BST树)
    反例: 二叉树的最长直径问题，需要获取左子树返回的信息，以及右子树返回的信息然后求出根节点的信息
**/
public class Solution {
    List<Integer> preOrder = new ArrayList<>();
    List<Integer> inOrder = new ArrayList<>();
    List<Integer> afterOrder = new ArrayList<>();
    public int[][] threeOrders (TreeNode root) {
        // write code here
        if(root == null) {
            return new int[3][0];
        }
        TreeNode cur = root;
        TreeNode mostRight;
        while(cur != null) {
            if(cur.left != null) {
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null) {  // 表明第一次遍历到左子树不为空的节点
                    mostRight.right = cur;
                     preOrder.add(cur.val);  // 先序遍历
                    cur = cur.left;
                    continue;
                } else {                // 表明第二次遍历到左子树不为空的节点 (后序遍历)
                    mostRight.right = null; 
                    printAfterNode(cur.left);  // 后续遍历
                }
            } else {      // 表明遍历到了左子树为空的节点，这个节点只会被遍历到一次
                 preOrder.add(cur.val);   // 先序遍历
            }
            // 中序遍历 输出遍历一次的节点 + 遍历两次的节点的第二次遍历 也即是左子树为空的节点先被遍历到,然后遍历到左子树不为空的第二次遍历
            inOrder.add(cur.val);
            cur = cur.right;
        }
        printAfterNode(root);
        int[][] ret = new int[3][preOrder.size()];
        for(int i = 0; i < preOrder.size(); i++) {
            ret[0][i] = preOrder.get(i);
            ret[1][i] = inOrder.get(i);
            ret[2][i] = afterOrder.get(i);
        }
        return ret;
    }
    // 打印对角线节点
    private void printAfterNode(TreeNode node) {
        TreeNode root = reverse(node);
        while(root != null) {
            afterOrder.add(root.val);
            root = root.right;
        }
        reverse(root);
    }
    // 反转链表
    private TreeNode reverse(TreeNode node) {
        TreeNode dummyNode = null;
        while(node != null) {
            TreeNode next = node.right;
            node.right = dummyNode;
            dummyNode = node;
            node = next;
        }
        return dummyNode;
    }
}