二叉樹遞歸迭代及morris層序前中后序遍歷詳解
分析二叉樹的前序，中序，后序的遍歷步驟
1.層序遍歷
方法一：廣度優(yōu)先搜索
? (以下解釋來自leetcode官方題解)
我們可以用廣度優(yōu)先搜索解決這個問題。
我們可以想到最樸素的方法是用一個二元組 (node, level) 來表示狀態(tài)，它表示某個節(jié)點和它所在的層數，每個新進隊列的節(jié)點的 level 值都是父親節(jié)點的 level 值加一。最后根據每個點的 level 對點進行分類，分類的時候我們可以利用哈希表，維護一個以 level 為鍵，對應節(jié)點值組成的數組為值，廣度優(yōu)先搜索結束以后按鍵 level 從小到大取出所有值，組成答案返回即可。
考慮如何優(yōu)化空間開銷：如何不用哈希映射，并且只用一個變量 node 表示狀態(tài)，實現這個功能呢？
我們可以用一種巧妙的方法修改廣度優(yōu)先搜索：
- ?首先根元素入隊
- ?當隊列不為空的時候,
求當前隊列的長度 S_i;?
依次從隊列中取 S_i?個元素進行拓展，然后進入下一次迭代.
它和普通廣度優(yōu)先搜索的區(qū)別在于，普通廣度優(yōu)先搜索每次只取一個元素拓展，而這里每次取 S_i個元素。在上述過程中的第 i?次迭代就得到了二叉樹的第?i 層的?S_i?個元素。
為什么這么做是對的呢？我們觀察這個算法，可以歸納出這樣的循環(huán)不變式：第 i 次迭代前，隊列中的所有元素就是第 i 層的所有元素，并且按照從左向右的順序排列。證明它的三條性質（你也可以把它理解成數學歸納法）：
初始化：i=1 的時候，隊列里面只有 root，是唯一的層數為 1 的元素，因為只有一個元素，所以也顯然滿足「從左向右排列」；
保持：如果 i=k 時性質成立，即第 k 輪中出隊 S_k的元素是第 k 層的所有元素，并且順序從左到右。因為對樹進行廣度優(yōu)先搜索的時候由低 k 層的點拓展出的點一定也只能是 k+1 層的點，并且 k+1 層的點只能由第 k 層的點拓展到，所以由這?S_k?個點能拓展到下一層所有的?S_k+1 ?個點。又因為隊列的先進先出（FIFO）特性，既然第 k 層的點的出隊順序是從左向右，那么第 k+1 層也一定是從左向右。至此，我們已經可以通過數學歸納法證明循環(huán)不變式的正確性。
終止：因為該循環(huán)不變式是正確的，所以按照這個方法迭代之后每次迭代得到的也就是當前層的層次遍歷結果。至此，我們證明了算法是正確的。
廣度優(yōu)先搜索的簡化步驟為
初始化隊列 q，并將根節(jié)點 root 加入到隊列中；
當隊列不為空時：
隊列中彈出節(jié)點 node，加入到結果中；
如果左子樹非空，左子樹加入隊列；
如果右子樹非空，右子樹加入隊列；
由于題目要求每一層保存在一個子數組中，所以我們額外加入了 level 保存每層的遍歷結果，并使用 for 循環(huán)來實現。
看個圖例用以說明：
廣度優(yōu)先需要用隊列作為輔助結構，我們先將根節(jié)點放到隊列中，然后不斷遍歷隊列。
首先拿出根節(jié)點，如果左子樹/右子樹不為空，就將他們放入隊列中。第一遍處理完后，根節(jié)點已經從隊列中拿走了，而根節(jié)點的兩個孩子已放入隊列中了，現在隊列中就有兩個節(jié)點 2 和 5。
第二次處理，會將 2 和 5 這兩個節(jié)點從隊列中拿走，然后再將 2 和 5 的子節(jié)點放入隊列中，現在隊列中就有三個節(jié)點 3，4，6。
我們把每層遍歷到的節(jié)點都放入到一個結果集中，最后返回這個結果集就可以了。
public List<List<Integer>> levelOrder(TreeNode root) {
//返回的結果
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(null == root){
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//根節(jié)點入隊
queue.add(root);
while(!queue.isEmpty()){
//一層的結果
List<Integer> level = new ArrayList<Integer>();
int levelCount = queue.size();
//添加節(jié)點到一層的List中去
for(int i = 0; i < levelCount ; i ++){
//節(jié)點出隊
TreeNode node = queue.remove();
//節(jié)點的左子樹入隊
if(node.left != null){
queue.add(node.left);
}
//節(jié)點的右子樹入隊
if(node.right != null){
queue.add(node.right);
}
level.add(node.val);
}
res.add(level);
}
return res;
}
方法二：遞歸
用廣度優(yōu)先處理是很直觀的，可以想象成是一把刀橫著切割了每一層，但是深度優(yōu)先遍歷就不那么直觀了。
我們開下腦洞，把這個二叉樹的樣子調整一下，擺成一個田字形的樣子。田字形的每一層就對應一個 list。
按照深度優(yōu)先的處理順序，會先訪問節(jié)點 1，再訪問節(jié)點 2，接著是節(jié)點 3。
之后是第二列的 4 和 5，最后是第三列的 6。
每次遞歸的時候都需要帶一個 index(表示當前的層數)，也就對應那個田字格子中的第幾行，如果當前行對應的 list 不存在，就加入一個空 list 進去。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
//將根節(jié)點放入隊列中，然后不斷遍歷隊列
queue.add(root);
while(queue.size()>0) {
//獲取當前隊列的長度，這個長度相當于 當前這一層的節(jié)點個數
int size = queue.size();
ArrayList<Integer> tmp = new ArrayList<Integer>();
//將隊列中的元素都拿出來(也就是獲取這一層的節(jié)點)，放到臨時list中
//如果節(jié)點的左/右子樹不為空，也放入隊列中
for(int i=0;i<size;++i) {
TreeNode t = queue.remove();
tmp.add(t.val);
if(t.left!=null) {
queue.add(t.left);
}
if(t.right!=null) {
queue.add(t.right);
}
}
//將臨時list加入最終返回結果中
res.add(tmp);
}
return res;
}
2.前序遍歷
2.1先輸出當前節(jié)點(初始的時候是root節(jié)點)
2.2如果左子節(jié)點不為空，則遞歸繼續(xù)前序遍歷
2.3如果右子節(jié)點不為空，則遞歸繼續(xù)前序遍歷
3.中序遍歷
3.1如果當前節(jié)點的左子節(jié)點不為空，則遞歸中序遍歷
3.2輸出當前節(jié)點
3.3如果當前節(jié)點的右子節(jié)點不為空，則遞歸中序遍歷
4.后序遍歷
4.1如果當前節(jié)點的左子節(jié)點不為空，則遞歸后序遍歷
4.2如果當前節(jié)點的右子節(jié)點不為空，則遞歸后序遍歷
4.3輸出當前節(jié)點
如果你按照 根節(jié)點 -> 左孩子 -> 右孩子 的方式遍歷，即「先序遍歷」，每次先遍歷根節(jié)點，遍歷結果為 1 2 4 5 3 6 7；
同理，如果你按照 左孩子 -> 根節(jié)點 -> 右孩子 的方式遍歷，即「中序序遍歷」，遍歷結果為 4 2 5 1 6 3 7；
如果你按照 左孩子 -> 右孩子 -> 根節(jié)點 的方式遍歷，即「后序序遍歷」，遍歷結果為 4 5 2 6 7 3 1；
最后，層序遍歷就是按照每一層從左向右的方式進行遍歷，遍歷結果為 1 2 3 4 5 6 7。
遞歸解法
由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法
前序遍歷--遞歸
public List<Integer> preorderTraversal(TreeNode root) {
//遞歸
List<Integer> list = new ArrayList<>();
preOrder(root,list);
return list;
}
public void preOrder(TreeNode root,List<Integer> list){
if(root == null){
return;
}
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
}
中序遍歷--遞歸
public List<Integer> inorderTraversal(TreeNode root) {
//遞歸
List<Integer> list = new LinkedList<>();
inOrder(root,list);
return list;
}
public void inOrder(TreeNode root,List<Integer> list){
if(root == null){
return;
}
inOrder(root.left,list);
list.add(root.val);
inOrder(root.right,list);
}
后序遍歷--遞歸
public List<Integer> postorderTraversal(TreeNode root) {
//遞歸
List<Integer> list = new LinkedList<>();
postOrder(root,list);
return list;
}
public void postOrder(TreeNode root,List<Integer> list){
if(root == null){
return;
}
postOrder(root.left,list);
postOrder(root.right,list);
list.add(root.val);
}
三種遞歸遍歷的總結：遞歸終止的條件為碰到空節(jié)點。
迭代解法
前序遍歷--迭代
核心思想：
1.每拿到一個節(jié)點就把它保存在棧中
2.繼續(xù)對這個節(jié)點的左子樹重復過程1，直到左子樹為空
3.因為保存在棧中的節(jié)點都遍歷了左子樹但是沒有遍歷右子樹，所以對棧中節(jié)點出棧并對它的右子樹重復過程1
4.直到遍歷完所有節(jié)點
public List<Integer> preorderTraversal(TreeNode root) {
//迭代
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
//臨時節(jié)點，幫助遍歷二叉樹
TreeNode node = root;
//棧的作用是用來短暫的保存遍歷節(jié)點的值，以助于最后值的返回
while(!stack.isEmpty() || node != null){
while(node != null){
list.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return list;
}
中序遍歷--迭代
public List<Integer> inorderTraversal(TreeNode root) {
//迭代
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
Deque<TreeNode> stack = new LinkedList<>();
while(!stack.isEmpty() || root != null){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);//出棧的時候才將父節(jié)點 的值加入到結果中
root = root.right;
}
return list;
}
和前序遍歷的代碼完全相同，只是在出棧的時候才將父節(jié)點?的值加入到結果中。
后序遍歷--迭代
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
list.addFirst(root.val);//addFirst():向鏈表首部添加元素
root = root.right;
} else {
root = stack.pop();
root = root.left;
}
}
return list;
}
三種迭代解法的總結：
前序遍歷和后序遍歷之間的關系：
前序遍歷順序為：根 -> 左 -> 右
后序遍歷順序為：左 -> 右 -> 根
如果1： 將前序遍歷中節(jié)點插入結果鏈表尾部的邏輯，修改為將節(jié)點插入結果鏈表的頭部
那么結果鏈表就變?yōu)榱耍河?-> 左 -> 根
如果2： 將遍歷的順序由從左到右修改為從右到左，配合如果1
那么結果鏈表就變?yōu)榱耍鹤?-> 右 -> 根
這剛好是后序遍歷的順序
基于這兩個思路，想一下如何處理：
修改前序遍歷代碼中，節(jié)點寫入結果鏈表的代碼，將插入隊尾修改為插入隊首
修改前序遍歷代碼中，每次先查看左節(jié)點再查看右節(jié)點的邏輯，變?yōu)橄炔榭从夜?jié)點再查看左節(jié)點
前序遍歷和中序遍歷之間的關系：
和前序遍歷的代碼完全相同，只是在出棧的時候才將父節(jié)點的值加入到結果中。
Morris遍歷
遍歷特點：Morris 遍歷利用了樹中大量空閑指針的特性
當前節(jié)點cur,一開始cur來到整樹頭
1）cur無左樹，cur? = cur.right（cur右移）
2）cur有左樹，找到左樹最右節(jié)點，mostright；此時我們又可以分為兩種情況，一種是葉子節(jié)點添加 right 指針的情況，一種是去除葉子節(jié)點 right 指針的情況
?A.mostright 的右指針指向null的mostright.right = cur,? cur = cur.left（cur左移）
?B.mostright 的右指針指向cur的mostright.right = null(為了防止重復執(zhí)行，則需要去掉 right 指針),? ????cur = cur.right（cur右移）
當cur == null時，整個過程結束。
遍歷特點：有左樹節(jié)點必遍歷到兩次，沒有左樹的節(jié)點必遍歷到一次
public static void morris(Node head){
if(head == null){
return;
}
Node cur = head;
Node mostRight = null;
while(cur != null){
//cur有沒有左樹
mostRight = cur.left;
if(mostRight != null){//有左樹的情況
//找到cur左樹上，真實的最右節(jié)點
//前者說明是第一次來到當前的cur，后者說明是第二次來到當前的cur
while(mostRight.right != null && mostRight.right != cur){
mostRight = mostRight.right;
}
//從while中出來，mostRight一定是cur左樹上的最右節(jié)點
if(mostRight.right == null){
mostRight.right = cur;
cur = cur.left;
continue;//結束的是外層的循環(huán)?。。。。。。。。。。。?！
}else{//走到這里意味著：mostRight.right == cur
mostRight.right = null;
}
}
//cur沒有左樹
cur = cur.right;
}
}
空間復雜度：利用空閑的指針，使用了兩個變量完成了遍歷，空間復雜度是常數級別的
時間復雜度：?
morris--前序遍歷
第一次來到一個節(jié)點，就打??；第二次來到這個節(jié)點，不打印
public static void morrisPre(Node head){
if(head == null){
return;
}
Node cur = head;
Node 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;
System.out.print(cur.value + " ");
cur = cur.left;
continue;
}else{
mostRight.right = null;
}
}else{
System.out.print(cur.value + " ");
}
cur = cur.right;
}
System.out.println();
}
morris--中序遍歷
對于能回到自己兩次的節(jié)點，第二次時打印，對于只能來到自己一次的節(jié)點，直接打印
只要一個節(jié)點要往右移動，就打印
public static void morrisIn(Node head){
if(head == null){
return;
}
Node cur = head;
Node 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.right = null;
}
}
System.out.print(cur.value + " ");
cur = cur.right;
}
System.out.println();
}
morris--后序遍歷：
public static void morrisPos(Node head) {
if(head == null) {
return;
}
Node cur = head;
Node 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.right = null;
printEdge(cur.left);//逆序打印左樹的右邊界
}
}
cur = cur.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);
}
private 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;
}
Morris后序遍歷比較復雜，可以看看相關的視頻講解--左神算法系列。
以上就是二叉樹遞歸迭代及morris層序前中后序遍歷詳解的詳細內容，更多關于二叉樹遞歸迭代遍歷詳解的資料請關注腳本之家其它相關文章！
相關文章
類和對象是兩種以計算機為載體的計算機語言的合稱。對象是對客觀事物的抽象，類是對對象的抽象。類是一種抽象的數據類型；變量就是可以變化的量，存儲在內存中—個可以擁有在某個范圍內的可變存儲區(qū)域2022-05-05
這篇文章主要介紹了IDEA連接mysql報錯的問題及解決方法,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
Gson是Google開發(fā)的一款Java?JSON處理庫，旨在簡化Java開發(fā)人員操作JSON數據的過程，本文就來和大家簡單聊聊Gson的原理與具體使用吧2023-05-05
Java class文件格式之方法_動力節(jié)點Java學院整理
這篇文章主要為大家詳細介紹了Java class文件格式之方法的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-06-06
SpringCloud之監(jiān)控數據聚合Turbine的實現
這篇文章主要介紹了SpringCloud之監(jiān)控數據聚合Turbine的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
詳解WebSocket+spring示例demo（已使用sockJs庫）
本篇文章主要介紹了WebSocket spring示例demo（已使用sockJs庫），小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
MappedByteBuffer使用虛擬內存，因此分配(map)的內存大小不受JVM的-Xmx參數限制，但是也是有大小限制的，這篇文章主要介紹了MappedByteBuffer的基本知識,需要的朋友可以參考下2022-12-12
這篇文章主要介紹了如何解決線程太多導致socket連接池出現的問題,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-12-12
MybatisPlus查詢條件為空字符串或null問題及解決
這篇文章主要介紹了MybatisPlus查詢條件為空字符串或null問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
這篇文章主要介紹了JAVA中的for循環(huán)幾種使用方法講解，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09