Morris遍历

一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)通过利用原树中大量空闲指针的方式，达到节省空间的目的
如果要遍历的树不能修改不可以用Morris遍历，但是Morris遍历完毕后会将树修改成原来的样子
Morris遍历解决了最本质的遍历问题，所以很多问题的最优解都以它为最优解

Morris遍历细节

假设来到当前节点cur，开始时cur来到头节点位置

  1. 如果cur没有左孩子，cur向右移动（cur = cur.right）
  2. 如果cur有左孩子，找到左子树上最右的节点mostRight：
    1. 如果mostRight的右指针指向空，让其指向cur，然后cur向左移动（cur = cur.left）
    2. 如果mostRight的右指针指向cur，让其指向null，然后cur向右移动（cur = cur.right）
  3. cur为空时遍历停止

  4. 一个节点如果有左数，一定会回到此节点两次，没有左数的节点只能到达一次

    1. public static void morris (Node head) {
    2.      if (head == null) {
    3.          return;
    4.      }
    5.      Node cur = head;
    6.      Node mostRight = null;
    7.      while (cur != null) { // 过流程
    8.          mostRight = cur.left; // mostRight是cur左孩子
    9.          if (mostRight != null) { // 有左子树
    10.              while (mostRight.right != null && mostRight.right != cur) {
    11.                  mostRight = mostRight.right;
    12.              }
    13.              // mostRight变成了cur左子树上，最右的节点
    14.              if (mostRight.right == null) { // 这是第一次来到cur
    15.                  mostRight.right = cur;
    16.                  cur = cur.left;
    17.                  continue;                    
    18.              } else { // mostRight.right == cur
    19.                  mostRight.right = null;
    20.              }
    21.          }
    22.          cur = cur.right;
    23.      }
    24.  }
    1. public class MorrisTraversal {
    3.  public static class Node {
    4.      public int value;
    5.      Node left;
    6.      Node right;
    8.      public Node(int data) {
    9.          this.value = data;
    10.      }
    11.  }
    12.  // 中序遍历
    13.  // 节点只来到一次的直接打印
    14.  // 节点来到两次的，第二次打印
    15.  public static void morrisIn(Node head) {
    16.      if (head == null) {
    17.          return;
    18.      }
    19.      Node cur1 = head;
    20.      Node mostRight = null;
    21.      while (cur1 != null) {
    22.          mostRight = cur1.left;
    23.          if (mostRight != null) {
    24.              while (mostRight.right != null && mostRight.right != cur1) {
    25.                  mostRight = mostRight.right;
    26.              }
    27.              if (mostRight.right == null) {
    28.                  mostRight.right = cur1;
    29.                  cur1 = cur1.left;
    30.                  continue;
    31.              } else {
    32.                  mostRight.right = null;
    33.              }
    34.          }
    35.          System.out.print(cur1.value + " ");
    36.          cur1 = cur1.right;
    37.      }
    38.      System.out.println();
    39.  }
    40.  // 先序遍历
    41.  // 只来到当前节点一次，直接打印
    42.  // 来到当前节点两次，第一次打印
    43.  public static void morrisPre(Node head) {
    44.      if (head == null) {
    45.          return;
    46.      }
    47.      Node cur1 = head;
    48.      Node mostRight = null;
    49.      while (cur1 != null) {
    50.          mostRight = cur1.left;
    51.          if (mostRight != null) {
    52.              while (mostRight.right != null && mostRight.right != cur1) {
    53.                  mostRight = mostRight.right;
    54.              }
    55.              if (mostRight.right == null) {
    56.                  mostRight.right = cur1;
    57.                  System.out.print(cur1.value + " ");
    58.                  cur1 = cur1.left;
    59.                  continue;
    60.              } else {
    61.                  mostRight.right = null;
    62.              }
    63.          } else {
    64.              System.out.print(cur1.value + " ");
    65.          }
    66.          cur1 = cur1.right;
    67.      }
    68.      System.out.println();
    69.  }
    70.  // 后序遍历的 做法：对于那些能第二次到达自己的节点，
    71.  // 逆序遍历其节点的左子树 的最右边界。  然后 最后补上整棵树的最右边界逆序。
    72.  public static void morrisPos(Node head) {
    73.      if (head == null) {
    74.          return;
    75.      }
    76.      Node cur1 = head;
    77.      Node mostRight = null;
    78.      while (cur1 != null) {
    79.          mostRight = cur1.left;
    80.          if (mostRight != null) {
    81.              while (mostRight.right != null && mostRight.right != cur1) {
    82.                  mostRight = mostRight.right;
    83.              }
    84.              if (mostRight.right == null) {
    85.                  mostRight.right = cur1;
    86.                  cur1 = cur1.left;
    87.                  continue;
    88.              } else {
    89.                  mostRight.right = null;
    90.                  printEdge(cur1.left);
    91.              }
    92.          }
    93.          cur1 = cur1.right;
    94.      }
    95.      printEdge(head);
    96.      System.out.println();
    97.  }
    98.  // 以X为头的树，逆序打印这棵树的右边界
    99.  public static void printEdge(Node head) {
    100.      Node tail = reverseEdge(head);
    101.      Node cur = tail;
    102.      while (cur != null) {
    103.          System.out.print(cur.value + " ");
    104.          cur = cur.right;
    105.      }
    106.      reverseEdge(tail);
    107.  }
    109.  public static Node reverseEdge(Node from) {
    110.      Node pre = null;
    111.      Node next = null;
    112.      while (from != null) {
    113.          next = from.right;
    114.          from.right = pre;
    115.          pre = from;
    116.          from = next;
    117.      }
    118.      return pre;
    119.  }
    121.  // for test -- print tree
    122.  public static void printTree(Node head) {
    123.      System.out.println("Binary Tree:");
    124.      printInOrder(head, 0, "H", 17);
    125.      System.out.println();
    126.  }
    128.  public static void printInOrder(Node head, int height, String to, int len) {
    129.      if (head == null) {
    130.          return;
    131.      }
    132.      printInOrder(head.right, height + 1, "v", len);
    133.      String val = to + head.value + to;
    134.      int lenM = val.length();
    135.      int lenL = (len - lenM) / 2;
    136.      int lenR = len - lenM - lenL;
    137.      val = getSpace(lenL) + val + getSpace(lenR);
    138.      System.out.println(getSpace(height * len) + val);
    139.      printInOrder(head.left, height + 1, "^", len);
    140.  }
    142.  public static String getSpace(int num) {
    143.      String space = " ";
    144.      StringBuffer buf = new StringBuffer("");
    145.      for (int i = 0; i < num; i++) {
    146.          buf.append(space);
    147.      }
    148.      return buf.toString();
    149.  }
    151.  public static void main(String[] args) {
    152.      Node head = new Node(4);
    153.      head.left = new Node(2);
    154.      head.right = new Node(6);
    155.      head.left.left = new Node(1);
    156.      head.left.right = new Node(3);
    157.      head.right.left = new Node(5);
    158.      head.right.right = new Node(7);
    159.      printTree(head);
    160.      morrisIn(head);
    161.      morrisPre(head);
    162.      morrisPos(head);
    163.      printTree(head);
    165.  }
    166. }

    Morris遍历判断一棵树是否是搜索二叉树

    public static boolean morrisIn(Node head) {
     if (head == null) {
         return true;
     }
     Node cur1 = head;
     Node mostRight = null;
     int preValue = Integer.MIN_VALUE;
     while (cur1 != null) {
         mostRight = cur1.left;
         if (mostRight != null) {
             while (mostRight.right != null && mostRight.right != cur1) {
                 mostRight = mostRight.right;
             }
             if (mostRight.right == null) {
                 mostRight.right = cur1;
                 cur1 = cur1.left;
                 continue;
             } else {
                 mostRight.right = null;
             }
         }
         //System.out.print(cur1.value + " ");
         if (cur.value <= preValue) {
             return false;
         }
         preValue = cur.value;
         cur1 = cur1.right;
     }
     return true;
 }

    树型dp套路和Morris遍历的使用区别：

  5. 如果发现某一个方法发现，必须来到某一个节点做第三次强整合（要完左树信息和要完右树信息，然后做强整合）则树型dp套路是最优解

  6. 如果不需要第三次强整合，则Morris遍历是最优解