面试中很值得聊的二叉树遍历方法——Morris遍历
xd会飞的猫 人气:1Morri遍历
通过利用空闲指针的方式，来节省空间。时间复杂度O(N)，额外空间复杂度O(1)。普通的非递归和递归方法的额外空间和树的高度有关，递归的过程涉及到系统压栈，非递归需要自己申请栈空间，都具有O(N)的额外空间复杂度。
Morri遍历的原则:
1. 假设当前节点为cur，
2. 如果cur没有左孩子，cur向右移动，cur = cur.right
3. 如果cur有左孩子，找到左子树上最右的节点mostRight
3.1 如果mostRight.right == null，令mostRight.right = cur，cur向左移动，cur = cur.left
3.2 如果mostRight.right == cur，令mostRight.right = null，cur向右移动，cur = cur.right
4. 如果cur == null 停止遍历
Morris：1242513637
1 public static void morris(TreeNode head){
2 if(head == null) return;
3 TreeNode cur = head;
4 TreeNode mostRight = null;
5 while(cur != null){//cur为空遍历停止【4】
6 mostRight = cur.left;//是cur左子树上最右的节点
7 if(mostRight != null){//有左子树【3】
8 while(mostRight.right != null && mostRight != cur){//mostRight!=cur不加就会绕环循环
9 mostRight = mostRight.right;//找最右节点【3】
10 }
11 if(mostRight.right == null){//第一次来到cur【3.1】
12 mostRight.right = cur;
13 cur = cur.left;
14 continue;//执行循环
15 }else {//mostRight.right = cur第二次来到cur【3.2】
16 mostRight.right = null;
17 }
18 }
19 cur = cur.right;//没有左子树【2】
20
21 }
22 }
所有节点遍历左子树右边界的时间总代价O(N)
基于Morris的先中后序遍历
如果cur有左子树一定能遍历2次，没有左子树只能遍历一次。
先序遍历
Morris：1242513637
Morris先序：1245367
基于Morris的先序遍历，如果一个节点可以到达两次则打印第一次，如果只能到达一次直接打印。
1 public static void morrisPre(TreeNode head){
2 if(head == null) return;
3 TreeNode cur = head;
4 TreeNode mostRight = null;
5 while(cur != null){//有左子树
6 mostRight = cur.left;
7 if(mostRight != null){
8 while(mostRight.right != null && mostRight != cur){
9 mostRight = mostRight.right;
10 }
11 if(mostRight.right == null){//第一次来到左子树
12 System.out.println(cur.val);//打印
13 mostRight.right = cur;
14 cur = cur.left;
15 continue;
16 }else {
17 mostRight.right = null;
18 }
19 }else{
20 System.out.println(cur.val);//没有左子树 只会遍历一次
21 }
22 cur = cur.right;
23 }
24 }
中序遍历
Morris：1242513637
Morris中序：4251637
基于Morris的中序遍历，如果一个节点可以到达两次则打印第二次，如果只能到达一次直接打印。
1 public static void morrisIn(TreeNode head) {
2 if(head == null) return;
3 TreeNode cur = head;
4 TreeNode mostRight = null;
5 while(cur != null){
6 mostRight = cur.left;
7 if(mostRight != null){
8 while(mostRight.right != null && mostRight != cur){
9 mostRight = mostRight.right;
10 }
11 if(mostRight.right == null){
12 mostRight.right = cur;
13 cur = cur.left;
14 continue;
15 }else {
16 mostRight.right = null;
17 }
18 }
19 //没有左树跳过if直接打印，有左树第二次来到cur退出循环打印
20 System.out.println(cur.val);
21 cur = cur.right;
22 }
23 }
后序遍历
Morris：1242513637
Morris先序：4526731
基于Morris的后序遍历，如果一个节点可以到达两次则第二次到达时逆序打印左树的右边界，单独逆序打印整棵树的右边界。
（1）逆序右边界（等同于单链表的逆序）
1 public static TreeNode reverseEdge(TreeNode from) {
2 TreeNode pre = null;
3 TreeNode next = null;
4 while(from != null){
5 next = from.right;
6 from.right = pre;
7 pre = from;
8 from = next;
9 }
10 return pre;
11 }
（2）逆序打印以head为头节点的右边界。
1 public static void printRightEdge(TreeNode head) {
2 TreeNode tail = reverseEdge(head);//逆转右边界
3 TreeNode cur = tail;
4 while(cur != null){
5 System.out.println(cur.val + " ");
6 cur = cur.right;
7 }
8 reverseEdge(tail);//逆转回去 恢复原树
9 }
（3）在Morris遍历中按时机打印。
1 public static void morrisPost(TreeNode head){
2 if(head == null) return;
3 TreeNode cur = head;
4 TreeNode mostRight = null;
5 while(cur != null){
6 mostRight = cur.left;
7 if(mostRight != null){
8 while(mostRight.right != null && mostRight != cur){
9 mostRight = mostRight.right;
10 }
11 if(mostRight.right == null){
12 mostRight.right = cur;
13 cur = cur.left;
14 continue;
15 }else {//第二次达到 逆序打印左子树的右边界
16 mostRight.right = null;
17 printRightEdge(cur.left);
18 }
19 }
20 cur = cur.right;
21 }
22 //最后退出循环之后，单独打印整棵树的右边界
23 printRightEdge(head);
24 }
Morris遍历的应用
如何判断一棵树是否是搜索二叉树？
中序遍历升序就是搜索二叉树。
1 public static boolean isBST(TreeNode head){
2 if(head == null) return true;
3 TreeNode cur = head;
4 TreeNode mostRight = null;
5 int preValue = Integer.MIN_VALUE;//上一次得到的值
6 while(cur != null){
7 mostRight = cur.left;
8 if(mostRight != null){
9 while(mostRight.right != null && mostRight != cur){
10 mostRight = mostRight.right;
11 }
12 if(mostRight.right == null){
13 mostRight.right = cur;
14 cur = cur.left;
15 continue;
16 }else {
17 mostRight.right = null;
18 }
19 }
20 //中序遍历的操作时机在这里 所以在这里进行判断
21 if(cur.val <= preValue){//没有递增
22 return false;
23 }
24 preValue = cur.val;
25 cur = cur.right;
26 }
27 return true;
28 }
总结
树型DP问题的套路：定义一个类收集树的信息，定义一个递归函数，递归地收集左子树的信息和右子树的信息，再整合得到以当前节点为根的树的信息。
什么时候用树型DP什么时候用Morris遍历？
当必须得到左树的信息和右树的信息后，再在当前节点整合二者信息后做出判断则用树型DP是最优解。
当不需要整合左树和右树信息的时候，可以用树型DP，但是Morris是最优解。
加载全部内容