二叉树的Morris遍历：先序遍历和中序遍历
二叉树的Morris遍历：先序遍历和中序遍历
提示：本节来说二叉树的Morris遍历，面试的高超优化技能！
此前学的关于二叉树的概念，先序遍历，中序遍历，后续遍历（这仨统称DFS遍历）和按层的方式遍历（俗称BFS遍历）重要的基础知识：
【1】二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现
【2】二叉树的宽度优先遍历BFS：按层的遍历方式，请你用队列实现DFS，或者请你用栈实现BFS
【3】求二叉树中，包含的最大二叉搜索子树的头节点是谁，它包含的节点数量是多少
这仨文章，都是重要的基础知识，笔试的时候可以用
面试的时候，除了上面仨，咱们还可以说一下Morris遍历的优化技能
Morris遍历的基础知识，有了这个知识，你才能看懂今天的题目解法
【4】Morris遍历：与二叉树的递归遍历（DFS/BFS）不同，优化空间复杂度为o(1)
题目
二叉树的Morris遍历：先序遍历
本题涉及的二叉树和节点如下：
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value = v;
}
}
//造树，长啥样呢：
// 1
// 2 3
// 4 5 6 7
public static Node createTree(){
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
head.left = n2;
head.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
return head;
}
Morris遍历
Morris遍历的基础知识，有了这个知识，你才能看懂今天的题目解法
【4】Morris遍历：与二叉树的递归遍历（DFS/BFS）不同，优化空间复杂度为o(1)
Morris遍历的流程：
（0）cur默认最开始指向head，mR默认为null【即cur左树的最右节点】，判断cur是否有左树？
（1）cur如果没有左树，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
（2）cur如果有左树，先找到左树的最右节点mR
（3）如果（2）中mR.right=null，则让mR.right=cur，cur=cur.left
（4）如果（2）中mR.right=cur,则让mR.right=null，然后cur=cur.right
Morris遍历手撕代码：
//复习Morris遍历
public static void morrisReview(Node head){
if (head == null) return;
//【随时熟悉Morris遍历】**Morris遍历的流程：**
//（0）cur默认最开始指向head，mR默认为null【即cur左树的最右节点】，判断cur是否有左树？
Node cur = head;
Node mR = null;
while (cur != null){
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//没左树的，跟（4）联合精简代码
mR = cur.left;//mR走一步先
//（2）cur如果**有左树**，先找到**左树的最右节点mR**
if (mR != null){
while (mR.right != null && mR.right != cur) mR = mR.right;//往右穿
//（3）如果（2）中mR.right=null，则让mR.right=cur，cur=cur.left
if(mR.right == null){//打印cur，这是第1次见面
mR.right = cur;
cur = cur.left;
continue;//绕过（4）
}else {//打印cur，这是第2次见面
mR.right = null;//mR.right=cur,则让mR.right=null，然后cur=cur.right
}
}
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//（4）如果（2）中mR.right=cur,则让mR.right=null，然后cur=cur.right
cur = cur.right;//因为（3）那continue，不会来着，否则（1）和（4）都要来
//这里加不加else都行，但是先序打印可能需要加else，1面就要打印
}
}
用Morris遍历完成二叉树的先序遍历
之前我们用DFS搞过先序遍历：
【1】二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现
一个规则：
遍历在Morris遍历第1次见cur时打印，就是先序遍历【当然，没有左树就见1次，直接打印】
遍历在Morris遍历第2次见cur时打印，就是中序遍历【当然，没有左树就见1次，直接打印】
手撕先序遍历代码，直接在Morris遍历上修改
//复习Morris遍历——先序遍历
//复习Morris遍历
public static void preMorrisReview(Node head){
if (head == null) return;
//【随时熟悉Morris遍历】**Morris遍历的流程：**
//（0）cur默认最开始指向head，mR默认为null【即cur左树的最右节点】，判断cur是否有左树？
Node cur = head;
Node mR = null;
while (cur != null){
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//没左树的，跟（4）联合精简代码
mR = cur.left;//mR走一步先
//（2）cur如果**有左树**，先找到**左树的最右节点mR**
if (mR != null){
while (mR.right != null && mR.right != cur) mR = mR.right;//往右穿
//（3）如果（2）中mR.right=null，则让mR.right=cur，cur=cur.left
if(mR.right == null){
//打印cur，这是第1次见面
System.out.print(cur.value +" ");
mR.right = cur;
cur = cur.left;
continue;//绕过（4）
}else mR.right = null;//mR.right=cur,则让mR.right=null，然后cur=cur.right
}
//打印cur，没有左树的就打印这1次，有左树的这是第2次见面不打印的
else System.out.print(cur.value +" ");//这个else一定加上
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//（4）如果（2）中mR.right=cur,则让mR.right=null，然后cur=cur.right
cur = cur.right;//因为（3）那continue，不会来着，否则（1）和（4）都要来
//这里加不加else都行，但是先序打印可能需要加else，1面就要打印
}
}
上面这个else，要注意哦，咱第2次见面不打印，只打印第一次见面，因为我们把没有左树的情况，和第二次见面的情况融合了，所以需要在区分开无左树的情况，就必须打，因为这就是第一次见面
测试一把：
//造树，长啥样呢：
// 1
// 2 3
// 4 5 6 7
public static void test(){
Node head = createTree();
Node head2 = createTree();
preMorris(head);
System.out.println();
preMorrisReview(head2);
}
public static void main(String[] args) {
test();
}
先序遍历：头，左，右
1 2 4 5 3 6 7
1 2 4 5 3 6 7
用Morris遍历完成二叉树的中序遍历
之前我们用DFS搞过中序遍历：
【1】二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现
一个规则：
遍历在Morris遍历第1次见cur时打印，就是先序遍历【当然，没有左树就见1次，直接打印】
遍历在Morris遍历第2次见cur时打印，就是中序遍历【当然，没有左树就见1次，直接打印】
跟先序遍历类似，手撕先序遍历代码，直接在Morris遍历上修改
咱们第一次见面不打印，但是也要注意，没左树是就必须打印，由于没左树和二次见面的代码是融合的，所以就直接在融合地方打印就行
//复习Morris遍历——中序遍历
//复习Morris遍历
public static void inMorrisReview(Node head){
if (head == null) return;
//【随时熟悉Morris遍历】**Morris遍历的流程：**
//（0）cur默认最开始指向head，mR默认为null【即cur左树的最右节点】，判断cur是否有左树？
Node cur = head;
Node mR = null;
while (cur != null){
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//没左树的，跟（4）联合精简代码
mR = cur.left;//mR走一步先
//（2）cur如果**有左树**，先找到**左树的最右节点mR**
if (mR != null){
while (mR.right != null && mR.right != cur) mR = mR.right;//往右穿
//（3）如果（2）中mR.right=null，则让mR.right=cur，cur=cur.left
if(mR.right == null){
mR.right = cur;
cur = cur.left;
continue;//绕过（4）
}else mR.right = null;//mR.right=cur,则让mR.right=null，然后cur=cur.right
}
//打印cur，没有左树的就打印这1次，有左树的这是第2次见面打印，就是中序遍历
System.out.print(cur.value +" ");//这个else一定加上
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//（4）如果（2）中mR.right=cur,则让mR.right=null，然后cur=cur.right
cur = cur.right;//因为（3）那continue，不会来着，否则（1）和（4）都要来
//这里加不加else都行，但是先序打印可能需要加else，1面就要打印
}
}
测试一把：
//造树，长啥样呢：
// 1
// 2 3
// 4 5 6 7
public static void test(){
Node head = createTree();
inMorris(head);
System.out.println();
Node head2 = createTree();
inMorrisReview(head2);
}
public static void main(String[] args) {
test();
}
左头右就是中序遍历
4 2 5 1 6 3 7
4 2 5 1 6 3 7
没得问题的
总结
提示：重要经验：
1）Morris遍历，有左树，见面2次，没左树，见面1次，一定要熟练掌握Morris遍历的代码，核心思想
2）先序遍历，第一次见面就打印，中序遍历，第2次见面就打印，不论中序还是先序，没左树的，只会见1次，直接打印即可
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
相关文章
- C++ 遍历进程窗口标题、窗口类名
- 数据结构基础 后序遍历和中序遍历还原二叉树
- C#中遍历Hashtable的4种方法
- shell遍历文件夹
- 二叉树的中序遍历
- 【Leetcode】102. 二叉树的层序遍历（中等）
- 二叉树的先序、中序和后序遍历
- 【Leetcode】105. 从前序与中序遍历序列构造二叉树（中等）
- 快速判断二叉树先序遍历 后序遍历
- 【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度：层次遍历+先序DFS+后序DFS[子问题分解]（C++版本）
- 数据结构——二叉树前序、中序、后序及层次四种遍历（java语言版）
- LintCode 二叉树的遍历 （非递归）
- 【Leetcode】105: 从前序与中序遍历序列构造二叉树
- [LeetCode] 314. Binary Tree Vertical Order Traversal 二叉树的竖直遍历
- [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树
- 二叉树的前序遍历，中序遍历，后序遍历学习 （原）
- leetcode 94. Binary Tree Inorder Traversal 二叉树的中序遍历(中等)
- leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树(中等)