Morris算法进行二叉树遍历

二叉树作为计算机中的一个重要数据结构，在很多领域都会涉及到，而提到二叉树，我们首先想到的就是其3种遍历方式--前序、中序和后序，对于这三种遍历方式，我们很容易通过使用递归或者迭代的方式实现，时间复杂度为O(N)。但是这两种实现方式都需要使用堆栈进行节点信息的存储，即空间复杂度也是O(N)。

但是还有一种更为巧妙的遍历方法Morris算法，该算法的时间复杂度也是O(N)，但是空间复杂度却能达到最优的O(1)。下面根据二叉树的三种遍历方式详细介绍Morris算法。

解决问题思路
1.初始化当前节点为current,一开始current来到整树头.
2.当前节点不为空:
(1)当前节点没有左孩子,currrent=current->right

(2)当前节点有左孩子,找到当前左子树的最右节点，记为mostright

• (a)如果mostright的right指针指向空(NULL)，让其指向cur(mostright.right=cur)，cur向左移动（cur=cur.left）
• (b)如果mostright的right指针指向cur，让其指向空(mostright.right=null)，cur向右移动（cur=cur.right）

根据需要的遍历顺序在不同的时机打印节点,后续遍历时需要返回转列表进行遍历.

• 初始化当前节点为current,一开始current来到整树头

初始化当前节点为current,一开始current来到整树头

image-20210627204036975

image-20210627204308739

image-20210627204534365

image-20210627204851911

image-20210627205157672

image-20210627205444942

image-20210627205740275

image-20210627205922167

image-20210627210122865

image-20210627210405872

Morris序，节点有左孩子，来到两次

image-20210627210900278

时间复杂度为O(N)，空间复杂度为O(1)。因为递归遍历二叉树会产生一个O(h)的递归栈的空间复杂度；要是用非递归使用栈来实现也是要产生一个O(h)的空间复杂度。所以morris遍历在二叉树遍历算是神级一般的算法了。

基础节点Code

public static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }

Morris遍历Code

public static void morris(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {//cur==null 循环结束
            // cur有没有左树
            mostRight = cur.left;
            if (mostRight != null) { // 有左树的情况下
                // 找到cur左树上，真实的最右
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;//找到当前左子树的最右节点，记为mostright
                }
                // 从while中出来，mostRight一定是cur左树上的最右节点
                // mostRight
                if (mostRight.right == null) {//如果mostright的right指针指向空(NULL)
                    mostRight.right = cur;//让其指向cur(mostright.right=cur)
                    cur = cur.left;//cur向左移动,（cur=cur.left）
                    continue;
                } else { // mostRight.right != null -> mostRight.right == cur
                    mostRight.right = null;
                }
            }
            cur = cur.right;//(1)当前节点没有左孩子,currrent=current->right
        }
    }

前序遍历：

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

后续遍历:

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

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

    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        Node cur = head;
        Node mostRight = null;
        Integer pre = null;
        boolean ans = true;
        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;
    }