左神提升5：Morris遍历

素颜马尾好姑娘i 2022-09-10 05:11 103阅读 0赞

## morris逻辑 ##

二叉树的棒状结构

保证当前的cur里面有值：
    	现在的当前节点记为cur，如果cur无左孩子，则cur向右移动，cur=cur.right
    	如果cur有左孩子，则找到左子树上最右的节点，记为mostright
    		1）如果mostright的右指针指向空，则让其指向cur，此时cur向左移动，cur = cur.left
    		2）如果mostright的左指针指向空，则让其指向空，cur向右移动

## morris原型 ##

public static void morris(Node head){
        
    	if(head == null){
        
    		return ;
    	}
    	Node cur = head;
    	Node mostright = null;
    	while(cur != null){
        
    		mostright = cur.left;
            	// 左树 不为空，那么就是会来到两次的节点，else是只能来一次的节点
    		if(mostright != null){
        
    			// 寻找左子树的最右的孩子
    			while(mostright.right != null && mostright.right != cur){
        
    				mostright = mostright.right;
    			}
    			// while跑完之后，找到左树的最右孩子，
    			// ① 为null变cur（cur还要跑到左边，继续whlie循环找最左节点）
    			// ② 为cur变null（cur已经跑上去了）
    			if(mostright.right == null){
          // 第一次来到
    				mostright.right = cur;
    				cur = cur.left;
    				continue;
    			}else{
                               // mostright=cur，第二次来到
    				mostright.right = null;
    			}
    		}
    		cur = cur.right;
    	}
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]

## 先序遍历 ##

> 要改成前序中序遍历，首先要知道有morris序，我们还需要知道有递归序  
> 可以参考一下：https://www.jianshu.com/p/00cc0b9ae4b4

【第一次来到、无左】输出

public class morris {
        
        public static void morris(TreeNode head) {
        
            if (head == null) {
        
                return;
            }
            TreeNode cur = head;
            TreeNode 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.println(cur.value);
                        mostright.right = cur;
                        cur = cur.left;
                        continue;
                    } else {
                               // mostright=cur，第二次来到
                        mostright.right = null;
                    }
                } else {
        
                    System.out.println(cur.value);
                }
                cur = cur.right;
            }
        }
    }

## 中序遍历： ##

中序遍历是 【*第二次来到、 无左*】就输出。

public static void morris(TreeNode head){
        
        if(head == null){
        
            return ;
        }
        TreeNode cur = head;
        TreeNode 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=cur，第二次来到
                    mostright.right = null;
                }
            }
            System.out.println(cur.value);
            cur = cur.right;
        }
    }

## 后序遍历 ##

public static void morrisPos(Node head){
        
    	if(head == null){
        
    		return;
    	}
    	Node cur1 = head;
    	Node cur2 = null;
    	while(cur1 != null){
        
    		cur2 = cur1.left;
    		if(cur2 != null){
        
    			while(cur2.right != null && cur2.right != cur1){
        
    				cur2 = cur2.right;
    			}
    			if(cur2.right == null){
        
    				cur2.right = cur1;
    				cur1 = cur1.left;
    				continue;
    			}else{
        
    				cur2.right = null;
    				//整个节点整棵树右节点逆序打印
    				printEdge(cur1.left);
    			}
    		}
    		cur1 = cur1.right;
    	}
    	//单独逆序打印右边边界，用逆转链表的形式更改，然后最后调整回来
    	printEdge(head);
    	System.out.println();
    }
    
    public static void printEdge(Node head) {
        
        Node tail = reverseEdge(head);
        Node cur = tail;
        while (cur != null) {
        
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        reverseEdge(tail);
    }
    
    public static Node reverseEdge(Node from) {
        
    	Node pre = null;
    	Node next = null;
    	while (from != null) {
        
    		next = from.right;
    		from.right = pre;
    		pre = from;
    		from = next;
    	}
    	return pre;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/b1ae417a123d411db8e13a862503d3cf.png