通常，實現(xiàn)二叉樹的前序（preorder）、中序（inorder）、后序（postorder）遍歷有兩個常用的方法：一是遞歸(recursive)，二是使用棧實現(xiàn)的迭代版本(stack+iterative)。這兩種方法都是O(n)的空間復(fù)雜度（遞歸本身占用stack空間或者用戶自定義的stack）。

本文介紹空間O(1)的遍歷方法。

上次文章講到，我們經(jīng)典遞歸遍歷其實有三次訪問當(dāng)前節(jié)點的機會，就看你再哪次進行操作，而分成了三種遍歷。

https://blog.csdn.net/hebtu666/article/details/82853988

morris有兩次訪問節(jié)點的機會。

它省空間的原理是利用了大量葉子節(jié)點的沒有用的空間，記錄之前的節(jié)點，做到了返回之前節(jié)點這件事情。

我們不說先序中序后序，先說morris遍歷的原則：

1、如果沒有左孩子，繼續(xù)遍歷右子樹

2、如果有左孩子，找到左子樹最右節(jié)點。

? ? 1）如果最右節(jié)點的右指針為空（說明第一次遇到），把它指向當(dāng)前節(jié)點，當(dāng)前節(jié)點向左繼續(xù)處理。

? ? 2）如果最右節(jié)點的右指針不為空（說明它指向之前結(jié)點），把右指針設(shè)為空，當(dāng)前節(jié)點向右繼續(xù)處理。

?

這就是morris遍歷。

請手動模擬深度至少為3的樹的morris遍歷來熟悉流程。

?

先看代碼：

定義結(jié)點：

public static class Node {public int value;Node left;Node right;public Node(int data) {this.value = data;}}

先序：

?（完全按規(guī)則寫就好。）

//打印時機（第一次遇到）：發(fā)現(xiàn)左子樹最右的孩子右指針指向空，或無左子樹。public static void morrisPre(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;System.out.print(cur1.value + " ");cur1 = cur1.left;continue;} else {cur2.right = null;}} else {System.out.print(cur1.value + " ");}cur1 = cur1.right;}System.out.println();}

morris在發(fā)表文章時只寫出了中序遍歷。而先序遍歷只是打印時機不同而已，所以后人改進出了先序遍歷。至于后序，是通過打印所有的右邊界來實現(xiàn)的：對每個有邊界逆序，打印，再逆序回去。注意要原地逆序，否則我們morris遍歷的意義也就沒有了。

完整代碼：?

public class MorrisTraversal {public static void process(Node head) {if(head == null) {return;}// 1//System.out.println(head.value);process(head.left);// 2//System.out.println(head.value);process(head.right);// 3//System.out.println(head.value);}public static class Node {public int value;Node left;Node right;public Node(int data) {this.value = data;}} //打印時機：向右走之前public static void morrisIn(Node head) {if (head == null) {return;}Node cur1 = head;//當(dāng)前節(jié)點Node cur2 = null;//最右while (cur1 != null) {cur2 = cur1.left;//左孩子不為空if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}//找到最右//右指針為空，指向cur1，cur1向左繼續(xù)if (cur2.right == null) {cur2.right = cur1;cur1 = cur1.left;continue;} else {cur2.right = null;}//右指針不為空，設(shè)為空}System.out.print(cur1.value + " ");cur1 = cur1.right;}System.out.println();} //打印時機（第一次遇到）：發(fā)現(xiàn)左子樹最右的孩子右指針指向空，或無左子樹。public static void morrisPre(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;System.out.print(cur1.value + " ");cur1 = cur1.left;continue;} else {cur2.right = null;}} else {System.out.print(cur1.value + " ");}cur1 = cur1.right;}System.out.println();} //逆序打印所有右邊界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;}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);morrisIn(head);morrisPre(head);morrisPos(head);}}

?

總結(jié)

以上是生活随笔為你收集整理的morris遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。