第30节.pptx
一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)
通过利用原树中大量空闲指针的方式，达到节省空间的目的
Morris 遍历步骤 :::danger 假设来到当前节点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为空时遍历停止 ::: Morris遍历实质 :::danger 建立一种机制：
    对于没有左子树的节点只到达一次，对于有左子树的节点会到达两次
    morris遍历时间复杂度依然是O(N) :::

    Morris遍历实现

    ```java public class Morris {

    private static class Node {

    1.  private Node left;
    2.  private Node right;
    3.  private int value;
    5.  public Node(int value) {
    6.      this.value = value;
    7.  }

    }

    // 递归遍历 先序 头-左-右

    public static void preProcess(Node head) {

     if (head == null) {
     return;
 }
 System.out.print(head.value + " ");
 preProcess(head.left);
 preProcess(head.right);

    }

    // 递归遍历 中序 左-头-右

    public static void inProcess(Node head) {

     if (head == null) {
     return;
 }
 inProcess(head.left);
 System.out.print(head.value + " ");
 inProcess(head.right);

    }

    // 递归遍历 后序 左-右-头

    public static void posProcess(Node head) {

     if (head == null) {
     return;
 }
 posProcess(head.left);
 posProcess(head.right);
 System.out.print(head.value + " ");

    }

    // 按层遍历

    public static void layerProcess(Node head) {

     if (head == null) {
     return;
 }
 Node[] queue = new Node[100];
 int inCursor = 0;
 int outCursor = 0;
 int count = 0;
 queue[inCursor++] = head;
 count++;
 while (count != 0) {
     inCursor = inCursor == 10 ? 0 : inCursor;
     outCursor = outCursor == 10 ? 0 : outCursor;
     Node cur = queue[outCursor++];
     count--;
     if (cur.left != null) {
         queue[inCursor++] = cur.left;
         count++;
     }
     if (cur.right != null) {
         queue[inCursor++] = cur.right;
         count++;
     }
     System.out.print(cur.value + " ");
 }

    }

// Moris遍历

/**
 * 假设来到当前节点cur，开始时cur来到头节点位置
 * 1 如果cur没有左孩子，cur向右移动(cur = cur.right)
 * 2 如果cur有左孩子，找到左子树上最右的节点mostRight：
 * a 如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)
 * b 如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)
 * 3 cur为空时遍历停止
 */

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) {
            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;
            }
        }
        cur = cur.right;
    }
}

// morris 遍历实现先序

public static void preMorris(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;
                System.out.print(cur.value + " ");
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        } else {
            System.out.print(cur.value + " ");
        }
        cur = cur.right;
    }
}


// morris 遍历实现中序

public static void inMorris(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;
    }
}

// Morris 遍历实现后序

public static void posMorris(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);
}

private static void printEdge(Node head) {
    Node tail = reverse(head);
    Node cur = tail;
    while (cur != null) {
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    reverse(tail);
}

private static Node reverse(Node node) {
    Node pre = null;
    Node next = null;
    while (node != null) {
        next = node.right;
        node.right = pre;
        pre = node;
        node = next;
    }
    return pre;
}

}

<a name="OQCVD"></a>
### 题目1：Morris遍历判断是否为搜索二叉树
```java
public static boolean isBST(Node head) {
    if (head == null) {
        return true;
    }
    Node cur = head;
    Node mostRight = null;
    boolean ans = true;
    Integer pre = 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;
            }
        }
        if (pre != null && pre >= cur.value) {
            ans = false;
        }
        pre = cur.value;
        cur = cur.right;
    }
    return ans;
}

题目2：二叉树最小深度

给定一棵二叉树的头节点head，求以head为头的树中，最小深度是多少？


private static class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int x) {
        val = x;
    }
}

public static int minHeight1(Node head) {
    if (head == null) {
        return 0;
    }
    return p(head);
}

// 返回x为头的树，最小深度是多少
public static int p(Node x) {
    if (x.left == null && x.right == null) {
        return 1;
    }
    // 左右子树起码有一个不为空
    int leftH = Integer.MAX_VALUE;
    if (x.left != null) {
        leftH = p(x.left);
    }
    int rightH = Integer.MAX_VALUE;
    if (x.right != null) {
        rightH = p(x.right);
    }
    return 1 + Math.min(leftH, rightH);
}

public static int minHeight2(Node head) {
    if (head == null) {
        return 0;
    }
    Node cur = head;
    Node mostRight = null;
    // 当前节点层数
    int curLevel = 0;
    // 最小高度
    int minHeight = Integer.MAX_VALUE;
    // Morris遍历
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            // 右节点的个数
            int rightBoardSize = 1;
            while (mostRight.right != null && mostRight.right != cur) {
                rightBoardSize++;
                mostRight = mostRight.right;
            }
            // 第一次到达
            if (mostRight.right == null) {
                curLevel++;
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else { // 第二次到达
                if (mostRight.left == null) {
                    minHeight = Math.min(minHeight, curLevel);
                }
                curLevel -= rightBoardSize;
                mostRight.right = null;
            }
        } else {
            // 只有一次到达
            curLevel++;
        }
        cur = cur.right;
    }
    int finalRight = 1;
    cur = head;
    while (cur.right != null) {
        finalRight++;
        cur = cur.right;
    }
    if (cur.left == null) {
        minHeight = Math.min(minHeight, finalRight);
    }
    return minHeight;
}