二叉树的Morris遍历

public static void morrisIn(TreeNode root) {
    if (root == null) return;
    TreeNode cur = root;
    TreeNode mostRight = null;
    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;
                cur = cur.left;
                continue;
            }else {
                mostRight.right = null;
            }
        }
        System.out.print(cur.val+" ");
        cur = cur.right;
    }
    System.out.println();
}

public static void morrisPre(TreeNode root) {
    if (root == null) return;
    TreeNode cur = root;
    TreeNode mostRight = null;
    while (cur != null){
        // 如果cur没有左孩子
        if (cur.left != null){
            mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            // 由于 如果 mostRight.right == null 那么这里必然是没有左孩子的cur
            if (mostRight.right == null){
                System.out.print(cur.val+" ");
                mostRight.right = cur;
                cur = cur.left;
                continue;
            }else {
                mostRight.right = null;
            }
        }else {
            //cur有左孩子，那么必然会经历两次，在第一次来的时候就打印
            System.out.print(cur.val+" ");
        }
        cur = cur.right;
    }
}