• 遍历二叉树不管是递归还是非递归， 时间复杂度都是O(N), 空间复杂度都是O(h)
  • Morris遍历能做到时间复杂度O（N）， 空间复杂度O（1）
  • 很多题目都跟树的遍历有关，掌握了morris遍历，往往就是题目的最优解就是基于Morris遍历的

Morris遍历

image.png

现在来过例子，把先序后序中序都先忘掉，现在只有morris序
image.png
image.png

image.png
image.png

我们要有个机制保证它不忘回穿
image.png

image.png
image.png
image.png
image.png

image.png
image.pngimage.pngimage.png
观察一下，如果一个节点有左孩子，它必然会被遍历到2次， 没有左孩子的点只会被遍历到1次
（如果有左树且左树的最右子节点是空， 那么我就是第一次来到当前节点，若左树的最右子节点指向的是自己，那么就说明是我第一次来到这个节点的时候改过它，那么这次就是第二次来到当前节点）
一个节点只要往右走它就再也不会回来了，它要么是往右要么是往上，

我们来看下时间复杂度
我们每个节点都要搞一下左树上的最右边界
image.png
一共有N个节点，每个节点都这么搞一遍, 还是O(N)吗？是的
image.png

  1.  public static class Node {
  2.      public int value;
  3.      Node left;
  4.      Node right;
  6.      public Node(int data) {
  7.          this.value = data;
  8.      }
  9.  }
  11. public static void morris(Node head) {
  12.     if (head == null) {
  13.         return;
  14.     }
  15.     Node cur = head;
  16.     Node mostRight = null;
  17.     while (cur != null) {
  18.         // cur 有没有左树
  19.         mostRight = cur.left;
  20.         if (mostRight != null) { // 有左树的情况下
  21.             // 找到cur左树上，真实的最右
  22.             while (mostRight.right != null && mostRight.right != cur) {
  23.                 mostRight = mostRight.right;
  24.             }
  25.             // 从while出来， mostRight一定是cur左树上的最右节点
  26.             if (mostRight.right == null) {
  27.                 mostRight.right = cur;
  28.                 cur = cur.left;
  29.                 continue;
  30.             } else { // mostRight.right --> cur
  31.                 mostRight.right = null;
  32.             }
  33.         }
  34.         cur = cur.right;
  35.     }
  36. }

先序

那么怎么加工出先序来呢？
你第一次来到节点的时候打印它，你就是先序，你第二次来到节点的时候打印它，你就是中序， 最后一次来到节点的时候才打印它， 那就是后序。

image.png

先序：
image.png

  1. public static void morrisPre(Node head) {
  2.         if (head == null) {
  3.             return;
  4.         }
  5.         Node cur = head;
  6.         Node mostRight = null;
  7.         while (cur != null) {
  8.             // cur 有没有左树
  9.             mostRight = cur.left;
  10.             if (mostRight != null) { // 有左树的情况下
  11.                 // 找到cur左树上，真实的最右
  12.                 while (mostRight.right != null && mostRight.right != cur) {
  13.                     mostRight = mostRight.right;
  14.                 }
  15.                 // 从while出来， mostRight一定是cur左树上的最右节点
  16.                 if (mostRight.right == null) {
  17.                     mostRight.right = cur;
  18.                     System.out.println(cur.value + " ");
  19.                     cur = cur.left;
  20.                     continue;
  21.                 } else { // mostRight.right --> cur
  22.                     mostRight.right = null;
  23.                 }
  24.             } else {
  25.                 System.out.println(cur.value + " ");
  26.             }
  27.             cur = cur.right;
  28.         }
  29.     }
  30.     public static class Node {
  31.         public int value;
  32.         Node left;
  33.         Node right;
  35.         public Node(int data) {
  36.             this.value = data;
  37.         }
  38.     }

中序：

对于能回到自己两次的节点，我们就让它第二次的时候打印，对于只能来到自己一次的节点，直接打印
image.pngimage.png
总结为只要节点往右移动就打印

  1. public static void morrisIn(Node head) {
  2.         if (head == null) {
  3.             return;
  4.         }
  5.         Node cur = head;
  6.         Node mostRight = null;
  7.         while (cur != null) {
  8.             // cur 有没有左树
  9.             mostRight = cur.left;
  10.             if (mostRight != null) { // 有左树的情况下
  11.                 // 找到cur左树上，真实的最右
  12.                 while (mostRight.right != null && mostRight.right != cur) {
  13.                     mostRight = mostRight.right;
  14.                 }
  15.                 // 从while出来， mostRight一定是cur左树上的最右节点
  16.                 if (mostRight.right == null) {
  17.                     mostRight.right = cur;
  18.                     cur = cur.left;
  19.                     continue;
  20.                 } else { // mostRight.right --> cur
  21.                     mostRight.right = null;
  22.                     System.out.println(cur.value + " ");
  23.                 }
  24.             }
  25.             cur = cur.right;
  26.         }
  27.     }
  28.     public static class Node {
  29.         public int value;
  30.         Node left;
  31.         Node right;
  33.         public Node(int data) {
  34.             this.value = data;
  35.         }
  36.     }

后序

接下来看后序：
打印时机就放在能回到自己两次的节点并且是在第二次回到的时候打印，
image.png
但不是打印它自己，而是打印它左树的右边界，逆序打印，
image.png
image.pngimage.png
这些时机的搞完之后，单独打印一下整棵树的有边界，逆序
image.png
（因为我们最后会错过整棵树的右边界）
为什么这样呢？
因为整棵树可以被子树的右边界分解掉

那我怎么逆序打印某棵树的有边界呢？
—-> 反转链表
image.png
image.png
image.png
然后打印，
打印完后再把树调回来
时间复杂度会不会因此变了？
不会，原来就是最多左树有边界过两次，现在变成4次
还是O（N）

  2. public static void morrisPos(Node head) {
  3.     if (head == null) {
  4.         return;
  5.     }
  6.     Node cur = head;
  7.     Node mostRight = null;
  8.     while (cur != null) {
  9.         // cur 有没有左树
  10.         mostRight = cur.left;
  11.         if (mostRight != null) { // 有左树的情况下
  12.             // 找到cur左树上，真实的最右
  13.             while (mostRight.right != null && mostRight.right != cur) {
  14.                 mostRight = mostRight.right;
  15.             }
  16.             // 从while出来， mostRight一定是cur左树上的最右节点
  17.             if (mostRight.right == null) {
  18.                 mostRight.right = cur;
  19.                 cur = cur.left;
  20.                 continue;
  21.             } else { // mostRight.right --> cur
  22.                 mostRight.right = null;
  23.                 printEdge(cur.left);
  24.             }
  25.         }
  26.         cur = cur.right;
  27.     }
  28.     printEdge(head);
  29. }
  31. public static class Node {
  32.         public int value;
  33.         Node left;
  34.         Node right;
  36.         public Node(int data) {
  37.             this.value = data;
  38.         }
  39. }
  41. public static void printEdge(Node head) {
  42.         Node tail = reverseEdge(head);
  43.         Node cur = tail;
  44.         while (cur != null) {
  45.             System.out.print(cur.value + " ");
  46.             cur = cur.right;
  47.         }
  48.         reverseEdge(tail);
  49. }
  51. public static Node reverseEdge(Node from) {
  52.     Node pre = null;
  53.     Node next = null;
  54.     while (from != null) {
  55.         next = from.right;
  56.         from.right = pre;
  57.         pre = from;
  58.         from = next;
  59.     }
  60.     return pre;
  61. }

题目：判断一棵树是不是搜索二叉树

中序遍历一下，如果数是一直递增的，那么就是搜索二叉树

  • 递归做法 ```java public boolean isValidBST(TreeNode root){ return isValidBST2(root, null, null); }

private boolean isValidBST2(TreeNode node, Integer minValue, Integer maxValue) { if (node == null) { return true; } if(minValue != null && node.val <= minValue) return false; if(maxValue != null && node.val >= maxValue) return false; if (! isValidBST2(node.left, minValue, node.val)) return false; if (! isValidBST2(node.right, node.val, maxValue)) return false; return true; }

  2. - morris做法
  3. ```java
  4. public boolean isValidBST2(TreeNode root){
  5.     if (root == null) {
  6.         return true;
  7.     }
  8.     TreeNode cur = root;
  9.     TreeNode mostRight = null;
  10.     Integer pre = null;
  11.     while (cur != null) {
  12.         // cur 有没有左树
  13.         mostRight = cur.left;
  14.         if (mostRight != null) { // 有左树的情况下
  15.             // 找到cur左树上，真实的最右
  16.             while (mostRight.right != null && mostRight.right != cur) {
  17.                 mostRight = mostRight.right;
  18.             }
  19.             // 从while出来， mostRight一定是cur左树上的最右节点
  20.             if (mostRight.right == null) {
  21.                 mostRight.right = cur;
  22.                 cur = cur.left;
  23.                 continue;
  24.             } else { // mostRight.right --> cur
  25.                 mostRight.right = null;
  26.             }
  27.         }
  28.         if (pre != null && pre >= cur.val) {
  29.             return false;
  30.         }
  31.         pre = cur.val;
  32.         cur = cur.right;
  33.     }
  34.     return true;
  35. }

题目：求二叉树最小高度

一颗二叉树，我想知道上面的最小高度，也就是所有叶节点中，哪个是距离头部最短的，把这个距离返回

二叉树递归解法

若我有左右子树， min（左，右） + 1
若有左无右 ， 左+ 1
若有右无左 右 + 1
若无左无右 1

public 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);
}

private 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);
}

用morris遍历改写

image.png
两个机制，1.怎么知道cur当前的高度， 2. 当cur是叶子节点的时候更新min

若cur无左树，下一步是要往右移动，level直接++
image.png
若cur有左树，且是第一次来到自己，那么它是怎么来到？ 可能是父节点往左来到，也可能是父节点往右来到
若cur有左树， 且是第二次来到自己，那么它只有是左子树的最右节点窜上来的， 那高度是什么，上一个节点高度减去它左子树最右节点的高度就是了， 举个例子
image.png
image.png
image.png
接下来又回到b了，上一个遍历的是d，d的高度已经是3了，减掉b左子树最右节点有几个点，就是高度了（3 - 1 =2）
image.png
image.png
然后e要窜回a了， （上一个节点）e的高度3 - 左树有边界有几个点 2 = 1
image.png
总结，如果是往下窜的，那么高度++准没错，若是从下面窜上来的，那么我们就要做减法

接下来第二个机制，我们能不能判断cur是不是真实的叶子节点？
判断不了了，因为到当你到叶子节点的时候，它的右指针一定是改过的，
举个例子
image.png
那我们怎么把所有叶子节点拿到呢？
所有叶子节点都会在回到上级第2次的时候重新发现一遍
举个例子
image.png
当我来到4的时候，什么也不管，对，就是什么也不管，错过了
然后我去到2，我知道是从下面窜上来的，我给它恢复完了之后，我再看看我左树的最右孩子是不是叶子节点，若是更新叶子节点高度， 若不是叶子节点就不参与更新，
也就是说，我是来到2的时候去抓4的高度，去更新全局min
image.png

但要注意的是，整棵树的最右节点是没有人去发现的，所以最后流程完，你要单独去找它

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;
    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 && cur.right == null) {
        minHeight = Math.min(minHeight, finalRight);
    }
    return minHeight;
}

什么情况下用不了Morris遍历？

当题的求解流程既需要左侧树的答案也需要右侧树的答案，空间一定不是O（1）的，
因为左子树的答案我得缓着，然后去收右子树的答案，

什么情况可以用Morris遍历

我不需要右侧树的答案，我只需要左侧树的答案，并且用完之后再也不需要它了