【算法&数据结构体系篇class30】：Morris遍历

你的名字 2024-03-23 15:21 72阅读 0赞

### 一、Morris遍历 ###

> **一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)**
> 
> **通过利用原树中大量空闲指针的方式，达到节省空间的目的**

### 二、Morris遍历细节 ###

> **假设来到当前节点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为空时遍历停止**

### 三、Morris遍历实质 ###

> 建立一种机制：
> 
> 对于没有左子树的节点只到达一次，
> 
> 对于有左子树的节点会到达两次
> 
> morris遍历时间复杂度依然是O(N)

### 四、代码演示 ###

package class30;
    
    
    /**Morris遍历
     *
     * 一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)
     *  
     * 通过利用原树中大量空闲指针的方式，达到节省空间的目的
     *
     * 假设来到当前节点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为空时遍历停止
     *
     *
     * Morris遍历实质
     * 建立一种机制：
     *
     * 对于没有左子树的节点只到达一次，
     *
     * 对于有左子树的节点会到达两次
     *  
     * morris遍历时间复杂度依然是O(N)
     */
    public class MorrisTraversal {
    
        //节点类
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int v) {
                value = v;
            }
        }
    
        public static void process(Node root) {
            if (root == null) {
                return;
            }
            // 1
            process(root.left);
            // 2
            process(root.right);
            // 3
        }
    
        //morris 遍历 空间复杂度O(1) 不需要像递归遍历需要栈空间  有左子树的节点 会遍历2回
        public static void morris(Node head) {
            if (head == null) return;
            Node cur = head;             //定义辅助变量cur指向头节点
            Node mostRight = null;       //表示当前cur节点的左子树的最右节点 初始值null
    
            //开始遍历 直到cur 来到null时跳出
            while (cur != null) {
                mostRight = cur.left;    //先让mostRight 指向当前节点左子节点
    
                //如果存在左子树 那么就接着遍历出左子树 最右节点
                if (mostRight != null) {
                    //继续往该左子树最右节点下沉 注意判断右节点 非空 并且 不指向当前节点cur 则继续下沉右节点
                    while (mostRight.right != null && mostRight.right != cur) {
                        mostRight = mostRight.right;
                    }
                    //跳出循环 那么就是两种情况 1.右节点指向为空 那么就需要指向cur  然后cur 下沉到左子树 然后继续while遍历
                    if (mostRight.right == null) {
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                    } else {
                        //否则 就是右指向为当前cur 说明此时是第二次来到cur  令指向为null cur向右子树走,向右走可以
                        mostRight.right = null;
                    }
                }
                //由于当 最右节点的右指向为 cur   或者 没有mostRight cur下的左树  两者情况都是 cur来到右指向
                //所以一句直接在 这个位置写 对其都生效 合并一句
                cur = cur.right;
            }
        }
    
    
        //morris 改先序遍历  基于morris遍历修改
        //没有左子树的节点 直接打印   有左子树的节点，在第一次遍历的时候打印    两处打印位置
        public static void morrisPre(Node head){
            if(head == null) return;
            Node cur = head;        //辅助变量 当前节点
            Node mostRight = null;  //当前节点的左子树最右边界
            while(cur != null){     //开始遍历 直到cur为空跳出 遍历完成
                mostRight = cur.left;  //赋值当前节点的左树
                if(mostRight != null){  //左树不为空
                    //左树的右节点不为空 且不为cur 那么就进行下沉 至最右节点
                    while(mostRight.right != null && mostRight.right != cur){
                        mostRight = mostRight.right;
                    }
                    //来到最右节点后 判断如果右节点为空 那么就指向cur  cur来到左树  然后跳过重新遍历
                    if(mostRight.right == null){
                        //注意： 这里就是 存在左树节点，且第一次遍历的位置 在这里进行打印
                        System.out.print(cur.value + " ");
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                    }else{
                        //右节点指向cur  那么指向就赋值null,相当于恢复原树结构 cur来到右树（该动作在104行进行 与其他条件合并使用同动作）  此时是存在左树节点 第二个遍历的位置
                        mostRight.right = null;
                    }
                }else {  //节点 没有左树 那么该节点直接打印
                    System.out.print(cur.value + " ");
                }
                //当节点 没有左树 或者在 有左树的情况下 其最右节点指向cur  两种情况下 我们需要将cur 指向其右树 继续遍历
                cur = cur.right;
            }
            System.out.println();
        }
    
        //morris 改中序遍历  基于morris遍历修改
        //没有左子树的节点 直接打印   有左子树的节点，在第二个次遍历的时候打印    两处打印位置  实际上在一个位置合并使用打印语句 一句即可
        public static void morrisIn(Node head){
            if(head == null) return;
            Node cur = head;        //辅助变量 当前节点
            Node mostRight = null;  //当前节点的左子树最右边界
            while(cur != null){     //开始遍历 直到cur为空跳出 遍历完成
                mostRight = cur.left;  //赋值当前节点的左树
                if(mostRight != null){  //左树不为空
                    //左树的右节点不为空 且不为cur 那么就进行下沉 至最右节点
                    while(mostRight.right != null && mostRight.right != cur){
                        mostRight = mostRight.right;
                    }
                    //来到最右节点后 判断如果右节点为空 那么就指向cur  cur来到左树 然后跳过重新遍历
                    if(mostRight.right == null){
                        //注意： 这里就是 存在左树节点，且第一次遍历的位置
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                    }else{
                        //右节点指向cur  那么指向就赋值null,相当于恢复原树结构 cur来到右树（该动作在104行进行 与其他条件合并使用同动作）  此时是存在左树节点 第二次遍历的位置
                        mostRight.right = null;
                    }
                }
                //当节点 没有左树 或者在 有左树的情况下 其最右节点指向cur  两种情况下 我们需要将cur 指向其右树 继续遍历
                //同时这个位置 没有左树 就直接打印   ； 有左树 且第二个来到的下行位置 第二个来到是在前面else判断部分，放在这个位置 等他前面判断完也是会经过的
                System.out.print(cur.value + " ");
                cur = cur.right;
            }
            System.out.println();
        }
    
        //morris 改后序遍历  基于morris遍历修改
        //有左子树的节点 在第二次遍历时 进行 逆序打印其左子树全部的右节点  最后在逆序打印整个树的全部右节点
        public static void morrisPos(Node head){
            if(head == null) return;
            Node cur = head;        //辅助变量 当前节点
            Node mostRight = null;  //当前节点的左子树最右边界
            while(cur != null){     //开始遍历 直到cur为空跳出 遍历完成
                mostRight = cur.left;  //赋值当前节点的左树
                if(mostRight != null){  //左树不为空
                    //左树的右节点不为空 且不为cur 那么就进行下沉 至最右节点
                    while(mostRight.right != null && mostRight.right != cur){
                        mostRight = mostRight.right;
                    }
                    //来到最右节点后 判断如果右节点为空 那么就指向cur  cur来到左树 然后跳过重新遍历
                    if(mostRight.right == null){
                        //注意： 这里就是 存在左树节点，且第一次遍历的位置
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                    }else{
                        //右节点指向cur  那么指向就赋值null,相当于恢复原树结构 cur来到右树（该动作在104行进行 与其他条件合并使用同动作）  此时是存在左树节点 第二次遍历的位置
                        mostRight.right = null;
    
                        //逆序打印当前节点 左树的全部右节点
                        printEdge(cur.left);
                    }
                }
                cur = cur.right;
            }
            //最后需要再逆序打印整个树的全部右节点
            printEdge(head);
            System.out.println();
        }
    
    
        //逆序打印 右节点
        public 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);
        }
    
        //逆序树结构 返回逆序后的头节点
        public static Node reverse(Node head){
            Node pre = null;
            Node next = null;
            while(head != null){
                next = head.right;
                head.right = pre;
                pre = head;
                head = next;
            }
            return pre;
        }
    
    
        // for test -- print tree
        public static void printTree(Node head) {
            System.out.println("Binary Tree:");
            printInOrder(head, 0, "H", 17);
            System.out.println();
        }
    
        public static void printInOrder(Node head, int height, String to, int len) {
            if (head == null) {
                return;
            }
            printInOrder(head.right, height + 1, "v", len);
            String val = to + head.value + to;
            int lenM = val.length();
            int lenL = (len - lenM) / 2;
            int lenR = len - lenM - lenL;
            val = getSpace(lenL) + val + getSpace(lenR);
            System.out.println(getSpace(height * len) + val);
            printInOrder(head.left, height + 1, "^", len);
        }
    
        public static String getSpace(int num) {
            String space = " ";
            StringBuffer buf = new StringBuffer("");
            for (int i = 0; i < num; i++) {
                buf.append(space);
            }
            return buf.toString();
        }
    
    
        /**
         * 判断是否是二叉搜索树  morris遍历 判断中序遍历是否节点都是升序排序的 是就是二叉搜索树
         * @param head
         * @return
         */
        public static boolean isBST(Node head) {
            if (head == null) {
                return true;
            }
            Node cur = head;
            Node mostRight = null;
            //注意 这里定义一个 前一个节点的的值 用来与后面cur当前节点做对比
            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;
                    }
                }
    
                //当前节点左树为空  节点就是往右节点接着遍历 这里我们就进行判断
                //中序遍历  也就是在这个位置打印节点值
                // 如果pre前节点非空 且 大于等于 当前节点的话 说明 节点不是升序 则不是二叉搜索树 返回false
                if (pre != null && pre >= cur.value) {
                    //注意需要把morris遍历完 再去返回 不能在这里遇到不符合就直接return 因为整个树结构的指向要恢复原结构
                    ans = false;
                }
                //如果符合 那么pre 就来到当前cur位置  cur接着向右节点
                pre = cur.value;
                cur = cur.right;
            }
            //若没有不符合的条件  遍历完之后 直接返回ans true
            return ans;
        }
    
        public static void main(String[] args) {
            Node head = new Node(4);
            head.left = new Node(2);
            head.right = new Node(6);
            head.left.left = new Node(1);
            head.left.right = new Node(3);
            head.right.left = new Node(5);
            head.right.right = new Node(7);
            printTree(head);
            morrisIn(head);
            morrisPre(head);
            morrisPos(head);
            printTree(head);
    
        }
    
    }

输出：

Binary Tree:
                                             v7v       
                            v6v       
                                             ^5^       
           H4H       
                                             v3v       
                            ^2^       
                                             ^1^       
    
    1 2 3 4 5 6 7 
    4 2 1 3 6 5 7 
    1 3 2 5 7 6 4 
    Binary Tree:
                                             v7v       
                            v6v       
                                             ^5^       
           H4H       
                                             v3v       
                            ^2^       
                                             ^1^       
    
    
    Process finished with exit code 0

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

>  **常规方法： 二叉树的递归解法**
> 
> **优化空间O(1): Morris遍历法**

package class30;
    
    /**
     * 给定一棵二叉树的头节点head
     *
     * 求以head为头的树中，最小深度是多少？   头节点到叶子节点
     *
     * https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
     */
    public class MinDepth {
    
        public static class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
    
            public TreeNode(int x) {
                val = x;
            }
        }
    
        // 下面的方法是一般解    递归返回最小深度是多少
        public static int minDepth1(TreeNode head) {
            //空树 高度0  一个根节点 高度1
            if(head == null) return 0;
            if(head.left == null && head.right == null) return 1;
    
            //定义深度变量 依次比较 左右子树递归的值  刷新高度的最小值
            int depth = Integer.MAX_VALUE;
            if(head.left != null){
                depth = Math.min(depth,minDepth1(head.left));
            }
            if(head.right != null){
                depth = Math.min(depth,minDepth1(head.right));
            }
            return 1 + depth;  //最后返回根节点1 加上子树的最小深度
        }
    
        // 下面的方法是morris遍历的解
        public static int minDepth2(TreeNode head) {
            if(head == null) return 0;
            TreeNode cur = head;
            TreeNode mostRight = null;
            int curLevel = 0;    //定义一个层级变量 初始为0
            int minHeight = Integer.MAX_VALUE;
            while (cur != null){
                mostRight = cur.left;
                if(mostRight != null){
                    int rightBoardSize = 1; //左子树非空 那么就定义一个长度 表示该左子树 依次往右的节点数 当前左子节点已经遍历 初始值1
                    //刷新左子树最右节点值  同时右节点数++
                    while (mostRight.right != null && mostRight.right!= cur){
                        rightBoardSize++;
                        mostRight = mostRight.right;
                    }
                    if(mostRight.right == null){
                        //第一次到达 然后刷新 指向cur  cur来到左节点 当前层级要++
                        curLevel++;
                        mostRight.right = cur;
                        cur = cur.left;
                        continue;
                   }else{//第二次到达
                        //如果是指向了cur  那么就需要判断 当前节点的左子树是否空 因为可能存在左树 如果不存在 那么就表示该节点是叶子节点
                        //可以进行高度的比较
                        if(mostRight.left == null){
                            //刷新当前层级与当前最小高度
                            minHeight = Math.min(curLevel,minHeight);
                        }
                        //此时因为是第二次到达 肯定是从小往上  那么层级就要减去 rightBoardSize 其右节点个数
                        curLevel -= rightBoardSize;
                        mostRight.right = null;   //指向再恢复为空
                    }
                }else{
                    // 左树为空 同时先把层级++ 最后再下面刷新cur指向右节点
                    curLevel++;
                }
                //节点没有左子树 获取有左子树 但是其最右侧节点指回了cur节点的时候 需要刷新cur 来到右节点继续遍历
                cur = cur.right;
            }
            //最后退出时，需要再判断下整个树是否有右节点 有的话 就进行判断其符合叶子节点 的高度
            int finalRight = 1;
            cur = head;  //cur节点重新指向头节点来遍历
            while (cur.right != null){  //遍历到最后一个右节点 cur保存
                finalRight++;
                cur = cur.right;
            }
            //遍历到最右的右节点 再判断 该节点是否存在左子树 只有不存在的时候 该节点才能作为叶子节点 与当前高度进行较小高度比较
            if(cur.left == null){
                minHeight = Math.min(finalRight,minHeight);
            }
            return minHeight;
        }
    }