Morris遍历

Morris遍历细节

• 
• 传统遍历方法的空间复杂度是O(树的高度)
• 利用底层叶节点的空指针节省空间
• 假如不允许修改题目给出的树就没法使用Morris遍历
• Morris遍历对于所有有左子树的节点都能到达两次
• 一个节点指针来到他的右子树之后就不会再次返回这个节点了
  • 判断第几次到达一个节点？
  • 根据左子树上最右节点的右指针指向谁，假如指向自己，那就是第二次到达

    public static void morris(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {// z有左孩子否则直接退回大循环
                while (mostRight.right != null && mostRight.right != cur) { // 找左树上的最右节点，右孩子不能等于当前节点
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {// 第一次来到cur
                    mostRight.right = cur;
                    cur = cur.left;//向左子树发展
                    continue;
                } else {
                    mostRight.right = null;// 第二次来到cur
                }
            }
            cur = cur.right;// 向右树移动
        }
    }

• 时间复杂度: O(N)

  Morris遍历改为先序遍历：

• 如果一个节点只能到达一次，直接打印内容
• 如果可以到达两次，第一次打印

  public static void morrisPre(Node head) {
      if (head == null) {
          return;
      }
      Node cur = head;
      Node mostRight = null;
      while (cur != null) {
          mostRight = cur.left;
          if (mostRight != null) {// 有左子树
              while (mostRight.right != null && mostRight.right != cur) {
                  mostRight = mostRight.right;
              }
              if (mostRight.right == null) {// 第一次来到这个节点
                  System.out.print(cur.value + " ");
                  mostRight.right = cur;
                  cur = cur.left;
                  continue;
              } else {// 第二次来，不打印
                  mostRight.right = null;
              }
          } else {// 没有左子树
              System.out.print(cur.value + " ");
          }
          cur = cur.right;
      }
      System.out.println();
  }

  中序遍历

• 只经过一次的节点：直接输出
• 两次的节点：第二次经过的时候打印

  public static void morrisIn(Node head) {
      if (head == null) {
          return;
      }
      Node cur = head;
      Node mostRight = null;
      while (cur != null) {
          mostRight = cur.left;
          if (mostRight != null) {
              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.value + " ");
          cur = cur.right;
      }
      System.out.println();
  }

  Morris后序遍历

• 将打印的时机安排在一个能回到自己两次的节点第二次被经过的时候
• 第二次回到自己的时候逆序打印自己左树的右边界
• 整个过程结束之后逆序打印整棵树的右边界

  逆序遍历如何实现

• 借用单链表逆序遍历的操作
• 指针逆序之后，打印然后再调整回去

  public static void morrisPos(Node head) {
      if (head == null) {
          return;
      }
      Node cur = head;
      Node mostRight = null;
      while (cur != null) {
          mostRight = cur.left;
          if (mostRight != null) {
              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;
                  printEdge(cur.left);// 第二次经过的时候逆序打印左树的右边界
              }
          }
          cur = cur.right;
      }
      printEdge(head);// 整个结束之后逆序打印整棵树的右边界
      System.out.println();
  }
  
  public static void printEdge(Node head) {// 打印然后再逆序回去
      Node tail = reverseEdge(head);
      Node cur = tail;
      while (cur != null) {
          System.out.print(cur.value + " ");
          cur = cur.right;
      }
      reverseEdge(tail);
  }
  
  public static Node reverseEdge(Node from) {// 单链表的逆序操作
      Node pre = null;
      Node next = null;
      while (from != null) {
          next = from.right;
          from.right = pre;
          pre = from;
          from = next;
      }
      return pre;
  }