二叉樹遞歸迭代及morris層序前中后序遍歷詳解
分析二叉樹的前序，中序，后序的遍歷步驟
1.層序遍歷
方法一：廣度優(yōu)先搜索
? (以下解釋來自leetcode官方題解)
我們可以用廣度優(yōu)先搜索解決這個問題。
我們可以想到最樸素的方法是用一個二元組 (node, level) 來表示狀態(tài)，它表示某個節(jié)點和它所在的層數(shù)，每個新進(jìn)隊列的節(jié)點的 level 值都是父親節(jié)點的 level 值加一。最后根據(jù)每個點的 level 對點進(jìn)行分類，分類的時候我們可以利用哈希表，維護(hù)一個以 level 為鍵，對應(yīng)節(jié)點值組成的數(shù)組為值，廣度優(yōu)先搜索結(jié)束以后按鍵 level 從小到大取出所有值，組成答案返回即可。
考慮如何優(yōu)化空間開銷：如何不用哈希映射，并且只用一個變量 node 表示狀態(tài)，實現(xiàn)這個功能呢？
我們可以用一種巧妙的方法修改廣度優(yōu)先搜索：
- ?首先根元素入隊
- ?當(dāng)隊列不為空的時候,
求當(dāng)前隊列的長度 S_i;?
依次從隊列中取 S_i?個元素進(jìn)行拓展，然后進(jìn)入下一次迭代.
它和普通廣度優(yōu)先搜索的區(qū)別在于，普通廣度優(yōu)先搜索每次只取一個元素拓展，而這里每次取 S_i個元素。在上述過程中的第 i?次迭代就得到了二叉樹的第?i 層的?S_i?個元素。
為什么這么做是對的呢？我們觀察這個算法，可以歸納出這樣的循環(huán)不變式：第 i 次迭代前，隊列中的所有元素就是第 i 層的所有元素，并且按照從左向右的順序排列。證明它的三條性質(zhì)（你也可以把它理解成數(shù)學(xué)歸納法）：
初始化：i=1 的時候，隊列里面只有 root，是唯一的層數(shù)為 1 的元素，因為只有一個元素，所以也顯然滿足「從左向右排列」；
保持：如果 i=k 時性質(zhì)成立，即第 k 輪中出隊 S_k的元素是第 k 層的所有元素，并且順序從左到右。因為對樹進(jìn)行廣度優(yōu)先搜索的時候由低 k 層的點拓展出的點一定也只能是 k+1 層的點，并且 k+1 層的點只能由第 k 層的點拓展到，所以由這?S_k?個點能拓展到下一層所有的?S_k+1 ?個點。又因為隊列的先進(jìn)先出（FIFO）特性，既然第 k 層的點的出隊順序是從左向右，那么第 k+1 層也一定是從左向右。至此，我們已經(jīng)可以通過數(shù)學(xué)歸納法證明循環(huán)不變式的正確性。
終止：因為該循環(huán)不變式是正確的，所以按照這個方法迭代之后每次迭代得到的也就是當(dāng)前層的層次遍歷結(jié)果。至此，我們證明了算法是正確的。
廣度優(yōu)先搜索的簡化步驟為
初始化隊列 q，并將根節(jié)點 root 加入到隊列中；
當(dāng)隊列不為空時：
隊列中彈出節(jié)點 node，加入到結(jié)果中；
如果左子樹非空，左子樹加入隊列；
如果右子樹非空，右子樹加入隊列；
由于題目要求每一層保存在一個子數(shù)組中，所以我們額外加入了 level 保存每層的遍歷結(jié)果，并使用 for 循環(huán)來實現(xiàn)。
看個圖例用以說明：
廣度優(yōu)先需要用隊列作為輔助結(jié)構(gòu)，我們先將根節(jié)點放到隊列中，然后不斷遍歷隊列。
首先拿出根節(jié)點，如果左子樹/右子樹不為空，就將他們放入隊列中。第一遍處理完后，根節(jié)點已經(jīng)從隊列中拿走了，而根節(jié)點的兩個孩子已放入隊列中了，現(xiàn)在隊列中就有兩個節(jié)點 2 和 5。
第二次處理，會將 2 和 5 這兩個節(jié)點從隊列中拿走，然后再將 2 和 5 的子節(jié)點放入隊列中，現(xiàn)在隊列中就有三個節(jié)點 3，4，6。
我們把每層遍歷到的節(jié)點都放入到一個結(jié)果集中，最后返回這個結(jié)果集就可以了。
public List<List<Integer>> levelOrder(TreeNode root) {
//返回的結(jié)果
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()){
//一層的結(jié)果
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)先遍歷就不那么直觀了。
我們開下腦洞，把這個二叉樹的樣子調(diào)整一下，擺成一個田字形的樣子。田字形的每一層就對應(yīng)一個 list。
按照深度優(yōu)先的處理順序，會先訪問節(jié)點 1，再訪問節(jié)點 2，接著是節(jié)點 3。
之后是第二列的 4 和 5，最后是第三列的 6。
每次遞歸的時候都需要帶一個 index(表示當(dāng)前的層數(shù))，也就對應(yīng)那個田字格子中的第幾行，如果當(dāng)前行對應(yīng)的 list 不存在，就加入一個空 list 進(jìn)去。
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) {
//獲取當(dāng)前隊列的長度，這個長度相當(dāng)于 當(dāng)前這一層的節(jié)點個數(shù)
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加入最終返回結(jié)果中
res.add(tmp);
}
return res;
}
2.前序遍歷
2.1先輸出當(dāng)前節(jié)點(初始的時候是root節(jié)點)
2.2如果左子節(jié)點不為空，則遞歸繼續(xù)前序遍歷
2.3如果右子節(jié)點不為空，則遞歸繼續(xù)前序遍歷
3.中序遍歷
3.1如果當(dāng)前節(jié)點的左子節(jié)點不為空，則遞歸中序遍歷
3.2輸出當(dāng)前節(jié)點
3.3如果當(dāng)前節(jié)點的右子節(jié)點不為空，則遞歸中序遍歷
4.后序遍歷
4.1如果當(dāng)前節(jié)點的左子節(jié)點不為空，則遞歸后序遍歷
4.2如果當(dāng)前節(jié)點的右子節(jié)點不為空，則遞歸后序遍歷
4.3輸出當(dāng)前節(jié)點
如果你按照 根節(jié)點 -> 左孩子 -> 右孩子 的方式遍歷，即「先序遍歷」，每次先遍歷根節(jié)點，遍歷結(jié)果為 1 2 4 5 3 6 7；
同理，如果你按照 左孩子 -> 根節(jié)點 -> 右孩子 的方式遍歷，即「中序序遍歷」，遍歷結(jié)果為 4 2 5 1 6 3 7；
如果你按照 左孩子 -> 右孩子 -> 根節(jié)點 的方式遍歷，即「后序序遍歷」，遍歷結(jié)果為 4 5 2 6 7 3 1；
最后，層序遍歷就是按照每一層從左向右的方式進(jìn)行遍歷，遍歷結(jié)果為 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é)：遞歸終止的條件為碰到空節(jié)點。
迭代解法
前序遍歷--迭代
核心思想：
1.每拿到一個節(jié)點就把它保存在棧中
2.繼續(xù)對這個節(jié)點的左子樹重復(fù)過程1，直到左子樹為空
3.因為保存在棧中的節(jié)點都遍歷了左子樹但是沒有遍歷右子樹，所以對棧中節(jié)點出棧并對它的右子樹重復(fù)過程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é)點 的值加入到結(jié)果中
root = root.right;
}
return list;
}
和前序遍歷的代碼完全相同，只是在出棧的時候才將父節(jié)點?的值加入到結(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;
}
三種迭代解法的總結(jié)：
前序遍歷和后序遍歷之間的關(guān)系：
前序遍歷順序為：根 -> 左 -> 右
后序遍歷順序為：左 -> 右 -> 根
如果1： 將前序遍歷中節(jié)點插入結(jié)果鏈表尾部的邏輯，修改為將節(jié)點插入結(jié)果鏈表的頭部
那么結(jié)果鏈表就變?yōu)榱耍河?-> 左 -> 根
如果2： 將遍歷的順序由從左到右修改為從右到左，配合如果1
那么結(jié)果鏈表就變?yōu)榱耍鹤?-> 右 -> 根
這剛好是后序遍歷的順序
基于這兩個思路，想一下如何處理：
修改前序遍歷代碼中，節(jié)點寫入結(jié)果鏈表的代碼，將插入隊尾修改為插入隊首
修改前序遍歷代碼中，每次先查看左節(jié)點再查看右節(jié)點的邏輯，變?yōu)橄炔榭从夜?jié)點再查看左節(jié)點
前序遍歷和中序遍歷之間的關(guān)系：
和前序遍歷的代碼完全相同，只是在出棧的時候才將父節(jié)點的值加入到結(jié)果中。
Morris遍歷
遍歷特點：Morris 遍歷利用了樹中大量空閑指針的特性
當(dāng)前節(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(為了防止重復(fù)執(zhí)行，則需要去掉 right 指針),? ????cur = cur.right（cur右移）
當(dāng)cur == null時，整個過程結(jié)束。
遍歷特點：有左樹節(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é)點
//前者說明是第一次來到當(dāng)前的cur，后者說明是第二次來到當(dāng)前的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;//結(jié)束的是外層的循環(huán)?。。。。。。。。。。。。?
}else{//走到這里意味著：mostRight.right == cur
mostRight.right = null;
}
}
//cur沒有左樹
cur = cur.right;
}
}
空間復(fù)雜度：利用空閑的指針，使用了兩個變量完成了遍歷，空間復(fù)雜度是常數(shù)級別的
時間復(fù)雜度：?
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后序遍歷比較復(fù)雜，可以看看相關(guān)的視頻講解--左神算法系列。
以上就是二叉樹遞歸迭代及morris層序前中后序遍歷詳解的詳細(xì)內(nèi)容，更多關(guān)于二叉樹遞歸迭代遍歷詳解的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
SpringBoot使用@RestController處理GET和POST請求的代碼詳解
在Spring?MVC中,@RestController注解的控制器類可以處理多種HTTP請求方法,包括GET和POST,所以本文就給大家詳細(xì)介紹了SpringBoot使用@RestController處理GET和POST請求的示例代碼,需要的朋友可以參考下2024-07-07
帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之隊列
這篇文章主要為大家介紹了Java數(shù)據(jù)結(jié)構(gòu)和算法之隊列，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要介紹了解決myBatis返回integer值的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-11-11
Maven是?個項目管理工具,基于POM(Project Object Model,項目對象模型)的概念,Maven可以通過一小段描述信息來管理項目的構(gòu)建,報告和文檔的項目管理工具軟件,很多新手還不夠了解maven,所以本文給大家講解Maven的使用和配置,需要的朋友可以參考下2025-04-04
在CentOS系統(tǒng)上安裝Java?JDK?8簡單步驟
最近購買一臺新的云服務(wù)器,用于開發(fā)學(xué)習(xí)使用,因此需要安裝很多的組件,下面這篇文章主要給大家介紹了關(guān)于在CentOS系統(tǒng)上安裝Java?JDK8的簡單步驟,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了JAVA 抽象類的相關(guān)資料，文中講解非常細(xì)致，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
一文解決springboot打包成jar文件無法正常運(yùn)行的問題
這篇文章主要介紹了一文解決springboot打包成jar文件無法正常運(yùn)行的問題,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
Spring如何消除代碼中的if-else/switch-case
這篇文章主要給大家介紹了關(guān)于Spring如何消除代碼中if-else/switch-case的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Spring具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
這篇文章主要介紹了如何將maven項目劃分為多個模塊，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-09-09
解析SpringBoot @EnableAutoConfiguration的使用
這篇文章主要介紹了解析SpringBoot @EnableAutoConfiguration的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09