題目：Binary Tree Inorder Traversal（二叉樹(shù)中序遍歷）

Given a binary tree, return the?inorder?traversal of its nodes' values.

給定一個(gè)二叉樹(shù)，返回它的?中序?遍歷。

Example:

Input:[1,null,2,3]1\2/3Output:[1,3,2]

Follow up:Recursive solution is trivial, could you do it iteratively?

進(jìn)階:?遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？

solve:

▉ 問(wèn)題分析

2）通常遞歸的方法解決二叉樹(shù)的遍歷最方便不過(guò)，但是我還是喜歡增加點(diǎn)難度，用一般的迭代循環(huán)來(lái)實(shí)現(xiàn)。

▉ 算法思路

遞歸法：

1）判斷當(dāng)前樹(shù)是否為空。

2）遞歸樹(shù)的左子樹(shù)結(jié)點(diǎn)。

3）輸出當(dāng)前結(jié)點(diǎn)的值。

4）遞歸樹(shù)的右子樹(shù)節(jié)點(diǎn)。

迭代循環(huán)法：

1）聲明一個(gè)棧，將樹(shù)的左子節(jié)點(diǎn)入棧。

2）每出棧一個(gè)結(jié)點(diǎn)，輸出當(dāng)前結(jié)點(diǎn)的值，且將該結(jié)點(diǎn)的右子樹(shù)進(jìn)行遍歷打印，保證每個(gè)出棧的結(jié)點(diǎn)輸出值之后，再輸出上一個(gè)左子節(jié)點(diǎn)之前，將當(dāng)前結(jié)點(diǎn)的右子節(jié)點(diǎn)遍歷畢。

3）整棵樹(shù)遍歷完畢的終止條件就是當(dāng)前棧是否存在結(jié)點(diǎn)（樹(shù)的左子節(jié)點(diǎn)）。

▉ 遞歸實(shí)現(xiàn)

varinorderTraversal =function(root){letarr = []constinorder =root=>{// 判斷當(dāng)前的結(jié)點(diǎn)是否為空if(root ==null)returnnull;// 遞歸左子樹(shù)inorder(root.left)// 輸出結(jié)點(diǎn)值arr.push(root.val)// 遞歸右子樹(shù)inorder(root.right)? ? }? ? inorder(root)returnarr};

▉ 迭代實(shí)現(xiàn)

// 迭代實(shí)現(xiàn)二叉樹(shù)的中序遍歷varinorderTraversal =function(root){letstack = [];letresult = [];while(true){// 判斷樹(shù)是否為空if(root ==null)returnresult;// 先將樹(shù)的左子節(jié)點(diǎn)推入棧中while(root !==null){? ? ? ? ? ? stack.push(root);? ? ? ? ? ? root = root.left;? ? ? ? }// 遍歷的終止條件if(stack.length !==0){// 輸出棧中的結(jié)點(diǎn)lettemp = stack.pop();? ? ? ? ? ? result.push(temp.val);// 如果當(dāng)前存在右子節(jié)點(diǎn)，要先打印右子樹(shù)節(jié)點(diǎn)root = temp.right;? ? ? ? }else{break;? ? ? ? }? ? }returnresult;}

進(jìn)群：697699179可以獲取Java各類(lèi)入門(mén)學(xué)習(xí)資料！

這是我的微信公眾號(hào)【編程study】各位大佬有空可以關(guān)注下，每天更新Java學(xué)習(xí)方法，感謝！

學(xué)習(xí)中遇到問(wèn)題有不明白的地方，推薦加小編Java學(xué)習(xí)群：697699179內(nèi)有視頻教程 ，直播課程 ，等學(xué)習(xí)資料，期待你的加入