随笔记录

算法-二叉树遍历-morris遍历

2022-5-10 diaba 算法

package com.jiucaiyuan.net.question;

import com.jiucaiyuan.net.algrithm.tree.Node;

/**
 * 【Morris遍历】
 * 一种遍历二叉树的方式，时间复杂度是O(N)，额外空间复杂度是O(1)
 * 通过利用原树中大量空闲指针的方式，达到节省空间的目的
 * 遍历过程中，更改了底层叶子结点指针，完成遍历后，恢复了指针指向
 *
 * @Author jiucaiyuan  2022/5/10 22:45
 * @mail services@jiucaiyuan.net
 */
public class Morris {
    /**
     * <pre>
     * 【Morris遍历】
     * 一种遍历二叉树的方式
     * 通过利用原树中大量空闲指针的方式，达到节省空间的目的
     * 二叉树的遍历算法
     * 【Morris遍历细节】
     * 假设来到当前节点curr，开始时curr来到头结点位置
     * 1）如果curr没有左孩子，curr向右移动（curr=curr.right）
     * 2）如果curr有左孩子，找到左子树上最右的节点mostRight:
     *      a.如果mostRight右指针指向null，让其指向curr，然后curr向左移动（curr = curr.left）
     *      b.如果mostRight右指针指向curr，让其指向null，然后curr向右移动（curr = curr.right）
     * 3）curr为空时遍历停止
     * 【复杂度分析】
     *      时间复杂度是O(N)
     *      额外空间复杂度是O(1)
     *  节点有左子树，会访问两次，如果没有左子树，只访问一次
     * </pre>
     *
     * @param head
     */
    public static void morris(Node<Integer> head) {
        if (head == null) {
            return;
        }
        Node curr = head;
        Node mostRight = null;
        while (curr != null) {
            System.out.print(curr.value + ",");  //morris 遍历序
            mostRight = curr.left;
            if (mostRight != null) {
                //最右指向不为空，且指向的不是自己，一直找左子树的最右节点
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                //截止到这里，mostRigt找到了左子树的最右侧节点
                if (mostRight.right == null) { //第一次访问最右侧节点
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                } else {  //否则，右指针一定指向当前节点的（判断是第二次访问当前节点
                    mostRight.right = null;//恢复左子树最右侧节点的默认值
                }
            }
            curr = curr.right;
        }
    }

    /**
     * morris遍历（前序遍历二叉树）
     * 由morris遍历序改成先序遍历，morris遍历时
     * 只访问一次的节点，直接打印
     * 访问两次的节点，第一次打印
     *
     * @param head
     */
    public static void morrisPre(Node head) {
        if (head == null) {
            return;
        }

        Node curr = head;
        Node mostRight = null;
        while (curr != null) {
            mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                //截止到这里，mostRigt找到了左子树的最右侧节点
                if (mostRight.right == null) { //第一次访问最右侧节点
                    System.out.print(curr.value + ",");
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                } else {
                    mostRight.right = null;//恢复左子树最右侧节点的默认值
                }
            } else {
                System.out.print(curr.value + ",");
            }
            curr = curr.right;
        }
    }

    /**
     * morris遍历（中序遍历二叉树）
     *
     * @param head
     */
    public static void morrisMid(Node head) {
        if (head == null) {
            return;
        }
        Node curr = head;
        Node mostRight = null;
        while (curr != null) {
            mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                //截止到这里，mostRigt找到了左子树的最右侧节点
                if (mostRight.right == null) { //第一次访问最右侧节点
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                } else {
                    System.out.print(curr.value + ",");
                    mostRight.right = null;//恢复左子树最右侧节点的默认值
                }
            } else {
                System.out.print(curr.value + ",");
            }
            curr = curr.right;
        }
    }

    /**
     * morris遍历（中序遍历二叉树）
     * 由morris遍历序改成中序遍历，morris遍历时
     * 只访问一次的节点，直接打印
     * 访问两次的节点，第二次打印
     *
     * @param head
     */
    public static void morrisIn(Node head) {
        if (head == null) {
            return;
        }
        Node curr = head;
        Node mostRight = null;
        while (curr != null) {
            mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                //截止到这里，mostRigt找到了左子树的最右侧节点
                if (mostRight.right == null) { //第一次访问最右侧节点
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                } else {
                    mostRight.right = null;//恢复左子树最右侧节点的默认值
                }
            }
            System.out.print(curr.value + ",");
            curr = curr.right;
        }
    }

    /**
     * morris遍历（后序遍历二叉树）
     * 由morris遍历序改成中序遍历，morris遍历时
     * 只访问一次的节点，不打印
     * 访问两次的节点，第一次访问时，不打印
     * 访问两次的节点，第二次访问时，逆序打印自己左树的右边界
     * 最后再统一逆序打印整棵树的右边界
     *
     * @param head
     */
    public static void morrisPost(Node head) {
        if (head == null) {
            return;
        }
        Node curr = head;
        Node mostRight = null;
        while (curr != null) {
            mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                //截止到这里，mostRigt找到了左子树的最右侧节点
                if (mostRight.right == null) { //第一次访问最右侧节点
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                } else {
                    mostRight.right = null;//恢复左子树最右侧节点的默认值
                    printEdge(curr.left); //逆序打印自己左树的右边界
                }
            }
            curr = curr.right;
        }
        printEdge(head); //逆序打印整棵树的右边界
        System.out.println();
    }

    /**
     * 逆序打印x为头结点的二叉树右边界
     *
     * @param x
     */
    public static void printEdge(Node<Integer> x) {
        Node<Integer> tail = reverseEdge(x);
        Node<Integer> curr = tail;
        while (curr != null) {
            System.out.println(curr.value + " ");
            curr = curr.right;
        }
        reverseEdge(tail);
    }

    /**
     * 把from——>from.right——>from.right.right单链表逆序
     *
     * @param from
     * @return 逆序后的头结点
     */
    public static Node<Integer> reverseEdge(Node<Integer> from) {
        Node<Integer> pre = null;
        Node<Integer> next = null;
        while (from != null) {
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }

    /**
     * morris遍历的应用
     * 判断一颗二叉树是否是搜索二叉树
     * （中序遍历时，遍历序列是升序的，即，左子树都比自己小，右子树都比自己大）
     * 时间复杂度 O(N)
     * 空间复杂度 O(1)
     *
     * @param head
     */
    public static boolean isBST(Node<Integer> head) {
        if (head == null) {
            return true;
        }
        Node<Integer> curr = head;
        Node mostRight = null;
        int preValue = Integer.MIN_VALUE;
        while (curr != null) {
            mostRight = curr.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                //截止到这里，mostRigt找到了左子树的最右侧节点
                if (mostRight.right == null) { //第一次访问最右侧节点
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                } else {
                    mostRight.right = null;//恢复左子树最右侧节点的默认值
                }
            }
//            System.out.print(curr.value + ",");
            //原本中序遍历打印的位置，做比较即可
            if (preValue >= curr.value) {
                return false;
            }
            curr = curr.right;
        }
        return true;
    }

    public static void main(String[] args) {
        Node head = new Node(1);

        Node left = new Node(2);
        Node right = new Node(3);

        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        head.left = left;
        head.right = right;

        left.left = node4;
        left.right = node5;
        right.left = node6;
        right.right = node7;

        morris(head);
        System.out.println();
        System.out.println("---------------------------");
        morrisPre(head);
        System.out.println();
        System.out.println("---------------------------");
        morrisMid(head);
        System.out.println();
        System.out.println("---------------------------");
        morrisIn(head);
    }
}