Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹前中后序遍歷非遞歸的具體實現(xiàn)詳解
一、前序遍歷
1.題目描述
給你二叉樹的根節(jié)點 root ，返回它節(jié)點值的 前序 遍歷。
2.輸入輸出示例
示例 1：
輸入：root = [1,null,2,3]
輸出：[1,2,3]
示例2：
輸入：root = []
輸出：[]
示例 3：
輸入：root = [1]
輸出：[1]
3.解題思路
前序遍歷：根結(jié)點—左子樹—右子樹
1.判斷額外情況，如果樹為空，直接返回
2.創(chuàng)建一個棧用來保存右子樹
3.先將根結(jié)點入棧，避免多次判斷棧為空
4.取出棧頂元素（第一次為根結(jié)點），從上往下遍歷最左側(cè)路徑中的每個結(jié)點
5.在遍歷時判斷當前結(jié)點的右子樹是否為空，非空則入棧
6.遍歷結(jié)束后，此時棧頂元素為前一個結(jié)點的右子樹，將棧頂元素取出，將其看作一棵樹，繼續(xù)重復上述操作，即形成循環(huán)。
4.代碼實現(xiàn)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
//創(chuàng)建一個棧用來保存右子樹
Stack<TreeNode> s=new Stack<>();
TreeNode cur=root;
s.push(root);
//從上往下遍歷最左側(cè)路徑中的每個結(jié)點，并將其右子樹保存起來---棧
while(!s.empty()||cur!=null){
cur=s.pop();
while(cur!=null){
list.add(cur.val);
if(cur.right!=null){
s.push(cur.right);
}
cur=cur.left;
}
}
return list;
}
}
二、中序遍歷
1.題目描述
給定一個二叉樹的根節(jié)點 root ，返回它的 中序 遍歷。
2.輸入輸出示例
示例 1：
輸入：root = [1,null,2,3]
輸出：[1,3,2]
示例 2：
輸入：root = []
輸出：[]
示例 3：
輸入：root = [1]
輸出：[1]
3.解題思路
中序遍歷：左子樹—根結(jié)點—右子樹
1.判斷額外情況，如果樹為空，直接返回
2.創(chuàng)建一個棧用來保存結(jié)點
3.從上往下遍歷最左側(cè)路徑中的每個結(jié)點，并將其保存到棧中，走到cur==null的位置
4.此時棧頂元素為最左側(cè)路徑的最后一個結(jié)點，將其加入到list并將棧頂元素移除
5.判斷最后一個結(jié)點的右子樹是否為空，過程和上述的過程是一樣的，直接將其右子樹看作一棵樹，整個過程便循環(huán)起來
4.代碼實現(xiàn)
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
Stack<TreeNode> s=new Stack<>();
TreeNode cur=root;
//從上往下遍歷最左側(cè)路徑中的每個結(jié)點，并將其保存到棧中
while(!s.empty()||cur!=null){
while(cur!=null){
s.push(cur);
cur=cur.left;
}
cur=s.pop();
list.add(cur.val);
cur=cur.right;
}
return list;
}
}
三、后序遍歷
1.題目描述
給定一個二叉樹，返回它的 后序 遍歷。
2.輸入輸出示例
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [3,2,1]
3.解題思路
后序遍歷：左子樹—右子樹—根結(jié)點
1.判斷額外情況，如果樹為空，直接返回
2.創(chuàng)建一個棧用來保存遍歷的結(jié)點
3找出以cur為根的二叉樹中最左側(cè)的節(jié)點，并保存所經(jīng)路徑中的所有結(jié)點—棧
4.此時棧頂元素為最左側(cè)路徑的最后一個結(jié)點
5.先要判斷最后一個結(jié)點的右子樹是否為空
如果為空，直接將結(jié)點加入list，同時將棧頂元素刪除
如果不為空則將右子樹看作一棵樹，重新進入循環(huán)判斷
注意：如果按照這樣，到了最后的右子樹就會一直循環(huán)出不來
解決方案：
創(chuàng)建一個prev用來標記已經(jīng)遍歷過的結(jié)點，將能否編歷的條件改為：top的右子樹為空||top的右子樹已經(jīng)遍歷過
4.代碼實現(xiàn)
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
Stack<TreeNode> s=new Stack<>();
TreeNode cur=root;
TreeNode prev=null;//用來標記剛剛遍歷過的節(jié)點
while(!s.empty()||cur!=null){
//1.找出以cur為根的二叉樹中最左側(cè)的節(jié)點，并保存所經(jīng)路徑中的所有節(jié)點---棧
while(cur!=null){
s.push(cur);
cur=cur.left;
}
TreeNode top=s.peek();
//top能否遍歷：top的右子樹為空||top的右子樹已經(jīng)遍歷過
if(top.right==null||top.right==prev){
list.add(top.val);
prev=top;
s.pop();
}else{
cur=top.right;
}
}
return list;
}
}
以上就是Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹前中后序遍歷非遞歸的具體實現(xiàn)詳解的詳細內(nèi)容，更多關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這里給大家分享了一個java常用的圖像處理工具類，包含縮放圖像、切割圖像、圖像類型轉(zhuǎn)換、彩色轉(zhuǎn)黑白、文字水印、圖片水印等，有需要的小伙伴參考下。2015-02-02
ThreadLocal是一個本地線程副本變量工具類。主要用于將私有線程和該線程存放的副本對象做一個映射，各個線程之間的變量互不干擾，特別適用于各個線程依賴不通的變量值完成操作的場景。下面我們來詳細了解一下它吧2019-06-06
java可變參數(shù)（不定向參數(shù)）的作用與實例
這篇文章主要給大家介紹了關(guān)于java可變參數(shù)（不定向參數(shù)）的作用與實例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
這篇文章主要介紹了IDEA在一個工作空間中管理多個項目的詳細步驟,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
java連接MySQL數(shù)據(jù)庫實現(xiàn)代碼
這篇文章主要為大家詳細介紹了java連接MySQL數(shù)據(jù)庫實現(xiàn)代碼，感興趣的小伙伴們可以參考一下2016-06-06
RabbitMQ的消息過期是基于追溯方式來實現(xiàn)的,也就是說當一個消息的TTL到期以后不一定會被移除或投遞到死信交換機,而是在消息恰好處于隊首時才會被處理,本篇文章給大家介紹spring boot Rabbit高級教程,感興趣的朋友一起看看吧2023-10-10
阿里Druid數(shù)據(jù)連接池引發(fā)的線上異常解決
這篇文章主要為大家介紹了一次關(guān)于阿里Druid數(shù)據(jù)連接池引發(fā)的線上異常問題的解決方案，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2022-03-03
Spring中@Autowired與@Resource的區(qū)別詳析
@Autowired與@Resource都可以用來裝配bean,都可以寫在字段上,或?qū)懺趕etter方法上,下面這篇文章主要給大家介紹了關(guān)于Spring中@Autowired與@Resource區(qū)別的相關(guān)資料,需要的朋友可以參考下2021-10-10
Mapstruct?@Mapper?@Mapping?使用小結(jié)
這篇文章主要介紹了Mapstruct?@Mapper?@Mapping使用小結(jié),他們用于各個對象實體間的相互轉(zhuǎn)換,例如數(shù)據(jù)庫底層實體轉(zhuǎn)為頁面對象,Model?轉(zhuǎn)為?DTO,?DTO?轉(zhuǎn)為其他中間對象,?VO?等等,相關(guān)轉(zhuǎn)換代碼為編譯時自動產(chǎn)生的新文件和代碼,需要的朋友可以參考下2023-09-09
本篇文章中主要介紹了java中實體類轉(zhuǎn)Json的2種方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧。2017-01-01