bin_tree_scan_morris.java

public class Node {
  int val;
  Node left;
  Node right;
}

public void inOrderScan(Node root) {
  if (root == null) return;
  
  Node cur = root;
  while (cur != null) {
    if (cur.left != null) {
      Node cur2 = cur.left;
      while (cur2.right != null && cur2.right != cur) {
        cur2 = cur2.right;
      }
      if (cur2.right == null) {
        cur2.right = cur;
        cur = cur.left;
        continue;
      } else {
        cur2.right = null;
      }
    }
    print(cur);
    cur = cur.right;
  }
}


public void preOrderScan(Node root) {
  if (root == null) return;
  
  Node cur = root;
  while (cur != null) {
    Node cur2 = cur.left;
    if (cur2 != null) {
      while (cur2.right != null && cur2.right != cur) {
        cur2 = cur2.right;
      }
      if (cur2.right == null) {
        cur2.right = cur;
        print(cur);
        cur = cur.left;
        continue;
      } else {
        cur2.right = null;
        cur = cur.right;
        continue;
      }
      
    } else {
      print(cur);
      cur = cur.right;
    }
}
  
  
public void postOrderScan(Node root) {
  if (root == null) return;
  
  Node cur = root;
  while (cur != null) {
    Node cur2 = cur.left;
    if (cur2 != null) {
      while (cur2.right != null && cur2.right != cur) {
        cur2 = cur2.right;
      }
      if (cur2.right == null) {
        cur2.right = cur;
        cur = cur.left;
        continue;
      } else {
        printReverseEdge(cur.left);
        cur2.right = null;
        cur = cur.right;
      }
    } else {
      cur = cur.right;
    }
  }
  
  printReverseEdge(root);
}