所谓Morris遍历，就是建立线索二叉树，然后在遍历的同时边建边拆。
主要思路就是，我先拿到当前节点，然后设置一个mostRight指向当前节点的左子树，然后不断地找右子树（这样做是为了找到当前节点的直接前驱节点）。找到之后，如果这个节点的右孩子指向为空，则指向当前节点，这就是建立线索二叉树；同时，为了不破坏二叉树的结构，当这个节点右孩子指向为当前节点时，我们就要把线索断掉，这就是拆。
左子树遍历完后，我们就需要遍历右子树。
具体可以看看视频教程：
我们直接来看代码：
1 package com.hw.list0710;
2
3 public class Morris {
4 static class TreeNode{
5 TreeNode left;
6 TreeNode right;
7 int val;
8 public TreeNode(int val, TreeNode left, TreeNode right){
9 this.val = val;
10 this.left = left;
11 this.right = right;
12 }
13 }
14
15 /**
16 * 先序遍历线索二叉树
17 * @param cur
18 */
19 private static void morrisPre(TreeNode cur){
20 if(cur == null){
21 return;
22 }
23 TreeNode mostRight = null;
24 while(cur != null)
25 {
26 mostRight = cur.left;
27 if(mostRight != null){
28 while(mostRight.right != null && mostRight.right != cur)
29 {
30 mostRight = mostRight.right;
31 }
32 if(mostRight.right == null){ //建立线索指针
33 mostRight.right = cur;
34 System.out.print(cur.val+" ");
35 cur = cur.left;
36 continue;
37 }else{
38 mostRight.right = null; //删除线索指针
39 }
40 }else{
41 System.out.print(cur.val+" ");
42 }
43 cur = cur.right; //左边没了，要到右边；左边遍历完了，也要到右边
44 }
45 }
46
47 /**
48 * 中序遍历线索二叉树
49 * @param cur
50 */
51 private static void morrisMid(TreeNode cur){
52 if(cur == null){
53 return;
54 }
55 TreeNode mostRight = null;
56 while(cur != null)
57 {
58 mostRight = cur.left;
59 if(mostRight != null){
60 while(mostRight.right != null && mostRight.right != cur)
61 {
62 mostRight = mostRight.right;
63 }
64 if(mostRight.right == null){
65 mostRight.right = cur;
66 cur = cur.left;
67 continue;
68 }else{
69 System.out.print(cur.val+" ");
70 mostRight.right = null;
71 }
72 }else{
73 System.out.print(cur.val+" ");
74 }
75 cur = cur.right;
76 }
77 }
78
79 /**
80 * 反转链表
81 * @param head
82 * @return
83 */
84 private static TreeNode reverse(TreeNode head){
85 TreeNode pre = null;
86 TreeNode cur, next;
87 cur = head;
88 while(cur != null)
89 {
90 next = cur.right;
91 cur.right = pre;
92 pre = cur; //指向当前节点的上一个节点的指针前移
93 cur = next;
94 }
95 return pre;
96 }
97
98 /**
99 * 打印链表节点
100 * @param head
101 */
102 private static void printNode(TreeNode head){
103 TreeNode tail = reverse(head);
104 while(tail != null)
105 {
106 System.out.print(tail.val+" ");
107 tail = tail.right;
108 }
109 reverse(tail);
110 }
111
112 /**
113 * 后序遍历线索二叉树
114 * @param cur
115 */
116 private static void morrisLast(TreeNode cur){
117 if(cur == null){
118 return;
119 }
120 TreeNode root = cur;
121 TreeNode mostRight = null;
122 while(cur != null)
123 {
124 mostRight = cur.left;
125 if(mostRight != null){
126 while(mostRight.right != null && mostRight.right != cur)
127 {
128 mostRight = mostRight.right;
129 }
130 if(mostRight.right == null){
131 mostRight.right = cur;
132 cur = cur.left;
133 continue;
134 }else{
135 mostRight.right = null;
136 printNode(cur.left);
137 }
138 }
139 cur = cur.right;
140 }
141 printNode(root);
142 }
143
144 public static void main(String[] args) {
145 TreeNode node6 = new TreeNode(6, null, null);
146 TreeNode node7 = new TreeNode(7, null, null);
147 TreeNode node5 = new TreeNode(5, node6, node7);
148 TreeNode node4 = new TreeNode(4, null, null);
149 TreeNode node2 = new TreeNode(2, node4, node5);
150 TreeNode node3 = new TreeNode(3, null, null);
151 TreeNode node1 = new TreeNode(1, node2, node3);
152 System.out.print("先序遍历:");
153 morrisPre(node1);
154 System.out.println();
155 System.out.print("中序遍历:");
156 morrisMid(node1);
157 System.out.println();
158 System.out.print("后序遍历:");
159 morrisLast(node1);
160 }
161 }