二叉树的普通遍历方式（递归和迭代）时间复杂度为O(n)，空间复杂度也为O(n)，在空间上这种方式通过压栈实现，所以空间复杂度为O(n)。
**Morris**遍历法可以在时间复杂度为O(n)的基础上，实现**O(1)**的空间复杂度（这是通过利用了二叉树中空闲的指针来实现的）。

Morris遍历通用逻辑

  1. public static void morris(Node head) {
  2.         if (null == head) {
  3.             return ;
  4.         }
  5.         Node cur = head;
  6.         //当前节点cur左子树的最右子节点
  7.         Node mostRight = null;
  8.         while (cur != null) {
  9.             mostRight = cur.left;
  10.             if (mostRight != null) {
  11.                 //找到cur左子树的最右子节点
  12.                 while (mostRight.right != null && mostRight.right != cur) {
  13.                     mostRight = mostRight.right;
  14.                 }
  15.                 //现在mostRight是左子树最右子节点
  16.                 if (mostRight.right == null) {
  17.                     //第一次来到cur
  18.                     //先将这个节点的右指针指向cur
  19.                     mostRight.right = cur;
  20.                     //转移cur
  21.                     cur = cur.left;
  22.                     continue;
  23.                 } else {
  24.                     //现在是第二次到达了cur节点，把第一次到达的时候设置的指针撤销
  25.                     mostRight.right = null;
  26.                 }
  27.             }
  28.             //没有左节点或第二次到达某个节点就转移到右节点
  29.             cur = cur.right;
  30.         }
  31.     }
  1. <br />`Morris`遍历的**前中后序**方案使用**一套通用代码 ，**主要的区别在于**在什么时机进行遍历操作**。

前序遍历

在每一个节点第一次遍历的时候进行打印操作。 

  1. public static void morrisPre(Node head) {
  2.         if (null == head) {
  3.             return ;
  4.         }
  5.         Node cur = head;
  6.         //当前节点cur左子树的最右子节点
  7.         Node mostRight = null;
  8.         while (cur != null) {
  9.             mostRight = cur.left;
  10.             if (mostRight != null) {
  11.                 //找到cur左子树的最右子节点
  12.                 while (mostRight.right != null && mostRight.right != cur) {
  13.                     mostRight = mostRight.right;
  14.                 }
  15.                 //现在mostRight是左子树最右子节点
  16.                 if (mostRight.right == null) {
  17.                     //树枝节点
  18.                     System.out.print(cur.val+" ");
  19.                     //第一次来到cur
  20.                     //先将这个节点的右指针指向cur
  21.                     mostRight.right = cur;
  22.                     //转移cur
  23.                     cur = cur.left;
  24.                     continue;
  25.                 } else {
  26.                     //现在是第二次到达了cur节点，把第一次到达的时候设置的指针撤销
  27.                     mostRight.right = null;
  28.                 }
  29.             } else {
  30.                 //叶子节点
  31.                 System.out.print(cur.val + " ");
  32.             }
  33.             //转移到右节点
  34.             cur = cur.right;
  35.         }
  36.     }

中序遍历

  • 只出现一次的节点直接打印
  • 出现两次的节点，在第二次出现的时候打印
    1. public static void morrisInOrder(Node head) {
    2.    if (null == head) {
    3.        return ;
    4.    }
    5.    Node cur = head;
    6.    //当前节点cur左子树的最右子节点
    7.    Node mostRight = null;
    8.    while (cur != null) {
    9.        mostRight = cur.left;
    10.        if (mostRight != null) {
    11.            //找到cur左子树的最右子节点
    12.            while (mostRight.right != null && mostRight.right != cur) {
    13.                mostRight = mostRight.right;
    14.            }
    15.            //现在mostRight是左子树最右子节点
    16.            if (mostRight.right == null) {
    17.                //第一次来到cur
    18.                //先将这个节点的右指针指向cur
    19.                mostRight.right = cur;
    20.                //转移cur
    21.                cur = cur.left;
    22.                continue;
    23.            } else {
    24.                //现在是第二次到达了cur节点，把第一次到达的时候设置的指针撤销
    25.                System.out.print(cur.val+" ");
    26.                mostRight.right = null;
    27.            }
    28.        } else {
    29.            //只出现一次
    30.            System.out.print(cur.val+" ");
    31.        }
    32.        //转移到右节点
    33.        cur = cur.right;
    34.    }
    35. }

    后序遍历

    在可以出现两次的节点的第二次出现的时候，逆序打印其左子树的右边路径（通过反转链表手段）。 
    1. public static void morrisPost(Node head) {
    2.    if (null == head) {
    3.        return ;
    4.    }
    5.    Node cur = head;
    6.    //当前节点cur左子树的最右子节点
    7.    Node mostRight = null;
    8.    while (cur != null) {
    9.        mostRight = cur.left;
    10.        if (mostRight != null) {
    11.            //找到cur左子树的最右子节点
    12.            while (mostRight.right != null && mostRight.right != cur) {
    13.                mostRight = mostRight.right;
    14.            }
    15.            //现在mostRight是左子树最右子节点
    16.            if (mostRight.right == null) {
    17.                //第一次来到cur
    18.                //先将这个节点的右指针指向cur
    19.                mostRight.right = cur;
    20.                //转移cur
    21.                cur = cur.left;
    22.                continue;
    23.            } else {
    24.                //现在是第二次到达了cur节点，把第一次到达的时候设置的指针撤销
    25.                mostRight.right = null;
    26.                //逆序打印左子树的右边界，通过翻转链表实现                    
    27.                reversePrint(cur.left);
    28.            }
    29.        }
    30.        //转移到右节点
    31.        cur = cur.right;
    32.    }
    33.    reversePrint(head);
    34. }
    35. public static void reversePrint(Node node) {
    36.    Node head = reverse(node);
    37.    Node current = head;
    38.    while (current!=null) {
    39.        System.out.print(current.val+" ");
    40.        current = current.right;
    41.    }
    42.    reverse(head);
    43. }
    44. public static Node reverse(Node node) {
    45.    Node head = node;
    46.    Node pre = null;
    47.    Node current = head;
    48.    while (current != null) {
    49.        Node right = current.right;
    50.        current.right = pre;
    51.        pre = current;
    52.        current = right;
    53.    }
    54.    return pre;
    55. }