//后序遍歷非遞歸：比中序遍歷多一個(gè)記錄節(jié)點(diǎn)last贰锁，用于記錄上一次返回的是不是從right節(jié)點(diǎn)返回馏臭。
public List<Integer> postorderTraversal_1(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if(root == null)
return ans;
TreeNode cur = root;
TreeNode last = null;
Stack<TreeNode> stack = new Stack<>();
while(cur != null || !stack.empty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.peek();
if(cur.right != null && cur.right != last){
cur = cur.right;
}else{
last = cur;
ans.add(cur.val);
stack.pop();
cur = null;
}
}
}
return ans;
}
//后序遍歷非遞歸：使用了先序遍歷的知識蛆橡，先序遍歷是根->左->右，后序遍歷是左->右->根，對于list的添加順序可以變成在隊(duì)列頭添加（根->右->左）弟翘，這樣隊(duì)列添加完就是左->右->根的順序了命斧。
public List<Integer> postorderTraversal_2(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if(root == null)
return ans;
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
stack.push(cur);
while(!stack.empty()){
cur = stack.pop();
if(cur.left != null){
stack.add(cur.left);
}
if(cur.right != null){
stack.add(cur.right);
}
ans.add(0, cur.val);
}
return ans;
}
//后序遍歷遞歸
public List<Integer> postorderTraversal_3(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if(root == null)
return ans;
subPostorderTraversal(root, ans);
return ans;
}
private void subPostorderTraversal(TreeNode root, List<Integer> ans){
if(root == null)
return;
subPostorderTraversal(root.left, ans);
subPostorderTraversal(root.right, ans);
ans.add(root.val);
}
后序遍歷遞歸和非遞歸-Java-LeetCode145
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來拙友，“玉大人为狸，你說我怎么就攤上這事∫牌酰” “怎么了辐棒？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長牍蜂。 經(jīng)常有香客問我漾根，道長，這世上最難降的妖魔是什么鲫竞？ 我笑而不...
- 正文 為了忘掉前任辐怕，我火速辦了婚禮，結(jié)果婚禮上从绘，老公的妹妹穿的比我還像新娘寄疏。我一直安慰自己其做，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布赁还。 她就那樣靜靜地躺著妖泄，像睡著了一般。 火紅的嫁衣襯著肌膚如雪艘策。 梳的紋絲不亂的頭發(fā)上蹈胡，一...
- 文/蒼蘭香墨 我猛地睜開眼青扔，長吁一口氣：“原來是場噩夢啊……” “哼源织！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起微猖，我...
- 序言：老撾萬榮一對情侶失蹤谈息，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后凛剥，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體侠仇，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年犁珠，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了逻炊。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
- 正文 年R本政府宣布，位于F島的核電站窑眯，受9級特大地震影響屏积，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜磅甩，卻給世界環(huán)境...
- 文/蒙蒙 一炊林、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧卷要，春花似錦渣聚、人聲如沸独榴。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽棺榔。三九已至，卻和暖如春隘道，著一層夾襖步出監(jiān)牢的瞬間症歇，已是汗流浹背。 一陣腳步聲響...
- 正文 我出身青樓激捏，卻偏偏與公主長得像设塔，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子远舅，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 注：本文來自 左程云的書《程序員代碼面試指南》 題目：分別用遞歸和非遞歸方法盖喷，實(shí)現(xiàn)二叉樹的先序遍歷(根左右)爆办、中序...
- 根據(jù)中序遍歷的順序，對于任一結(jié)點(diǎn)课梳，優(yōu)先訪問其左孩子距辆，而左孩子結(jié)點(diǎn)又可以看做一根結(jié)點(diǎn)，然后繼續(xù)訪問其左孩子結(jié)點(diǎn)暮刃，直到...
- 一、生成二叉樹 新建一個(gè)類： 生成二叉樹方法： 生成二叉樹： 二氧猬、前序遍歷 前序遍歷：訪問順序是【根節(jié)點(diǎn)】-【左孩...
- 過年回家背犯，免不了會被親人問起，你是做什么的盅抚？作為一個(gè)數(shù)據(jù)技術(shù)從業(yè)者漠魏，面對沒怎么接觸過電腦，對電腦使用都不太熟悉的親...
