用迭代法編寫二叉樹的前后中序遍歷案例

二叉樹的迭代遍歷

看完本篇大家可以使用迭代法，再重新解決如下三道leetcode上的題目：

144.二叉樹的前序遍歷

94.二叉樹的中序遍歷

145.二叉樹的后序遍歷

為什么可以用迭代法（非遞歸的方式）來實(shí)現(xiàn)二叉樹的前后中序遍歷呢？

我們?cè)跅Ｅc隊(duì)列：匹配問題都是棧的強(qiáng)項(xiàng)中提到了，遞歸的實(shí)現(xiàn)就是：每一次遞歸調(diào)用都會(huì)把函數(shù)的局部變量、參數(shù)值和返回地址等壓入調(diào)用棧中，然后遞歸返回的時(shí)候，從棧頂彈出上一次遞歸的各項(xiàng)參數(shù)，所以這就是遞歸為什么可以返回上一層位置的原因。

此時(shí)大家應(yīng)該知道我們用棧也可以是實(shí)現(xiàn)二叉樹的前后中序遍歷了。

前序遍歷（迭代法）

我們先看一下前序遍歷。

前序遍歷是中左右，每次先處理的是中間節(jié)點(diǎn)，那么先將跟節(jié)點(diǎn)放入棧中，然后將右孩子加入棧，再加入左孩子。

為什么要先加入 右孩子，再加入左孩子呢？因?yàn)檫@樣出棧的時(shí)候才是中左右的順序。

動(dòng)畫如下：

不難寫出如下代碼: （注意代碼中空節(jié)點(diǎn)不入棧）

class?Solution?{
public:
????vector?preorderTraversal(TreeNode*?root)?{
????????stack?st;
????????vector?result;
????????if?(root?==?NULL)?return?result;
????????st.push(root);
????????while?(!st.empty())?{
????????????TreeNode*?node?=?st.top();???????????????????????//?中
????????????st.pop();
????????????result.push_back(node->val);
????????????if?(node->right)?st.push(node->right);???????????//?右（空節(jié)點(diǎn)不入棧）
????????????if?(node->left)?st.push(node->left);?????????????//?左（空節(jié)點(diǎn)不入棧）
????????}
????????return?result;
????}
};

此時(shí)會(huì)發(fā)現(xiàn)貌似使用迭代法寫出前序遍歷并不難，確實(shí)不難。

此時(shí)是不是想改一點(diǎn)前序遍歷代碼順序就把中序遍歷搞出來了？

其實(shí)還真不行！

但接下來，再用迭代法寫中序遍歷的時(shí)候，會(huì)發(fā)現(xiàn)套路又不一樣了，目前的前序遍歷的邏輯無法直接應(yīng)用到中序遍歷上。

中序遍歷（迭代法）

為了解釋清楚，我說明一下 剛剛在迭代的過程中，其實(shí)我們有兩個(gè)操作：

處理：將元素放進(jìn)result數(shù)組中

訪問：遍歷節(jié)點(diǎn)

分析一下為什么剛剛寫的前序遍歷的代碼，不能和中序遍歷通用呢，因?yàn)榍靶虮闅v的順序是中左右，先訪問的元素是中間節(jié)點(diǎn)，要處理的元素也是中間節(jié)點(diǎn)，所以剛剛才能寫出相對(duì)簡潔的代碼，因?yàn)橐L問的元素和要處理的元素順序是一致的，都是中間節(jié)點(diǎn)。

那么再看看中序遍歷，中序遍歷是左中右，先訪問的是二叉樹頂部的節(jié)點(diǎn)，然后一層一層向下訪問，直到到達(dá)樹左面的最底部，再開始處理節(jié)點(diǎn)（也就是在把節(jié)點(diǎn)的數(shù)值放進(jìn)result數(shù)組中），這就造成了處理順序和訪問順序是不一致的。

那么在使用迭代法寫中序遍歷，就需要借用指針的遍歷來幫助訪問節(jié)點(diǎn)，棧則用來處理節(jié)點(diǎn)上的元素。

動(dòng)畫如下：

中序遍歷，可以寫出如下代碼：

class?Solution?{
public:
????vector?inorderTraversal(TreeNode*?root)?{
????????vector?result;
????????stack?st;
????????TreeNode*?cur?=?root;
????????while?(cur?!=?NULL?||?!st.empty())?{
????????????if?(cur?!=?NULL)?{?//?指針來訪問節(jié)點(diǎn)，訪問到最底層
????????????????st.push(cur);?//?將訪問的節(jié)點(diǎn)放進(jìn)棧
????????????????cur?=?cur->left;????????????????//?左
????????????}?else?{
????????????????cur?=?st.top();?//?從棧里彈出的數(shù)據(jù)，就是要處理的數(shù)據(jù)（放進(jìn)result數(shù)組里的數(shù)據(jù)）
????????????????st.pop();
????????????????result.push_back(cur->val);?????//?中
????????????????cur?=?cur->right;???????????????//?右
????????????}
????????}
????????return?result;
????}
};

后序遍歷（迭代法）

再來看后序遍歷，先序遍歷是中左右，后續(xù)遍歷是左右中，那么我們只需要調(diào)整一下先序遍歷的代碼順序，就變成中右左的遍歷順序，然后在反轉(zhuǎn)result數(shù)組，輸出的結(jié)果順序就是左右中了，如下圖：

所以后序遍歷只需要前序遍歷的代碼稍作修改就可以了，代碼如下：

class?Solution?{
public:
????vector?postorderTraversal(TreeNode*?root)?{
????????stack?st;
????????vector?result;
????????if?(root?==?NULL)?return?result;
????????st.push(root);
????????while?(!st.empty())?{
????????????TreeNode*?node?=?st.top();
????????????st.pop();
????????????result.push_back(node->val);
????????????if?(node->left)?st.push(node->left);?//?相對(duì)于前序遍歷，這更改一下入棧順序?（空節(jié)點(diǎn)不入棧）
????????????if?(node->right)?st.push(node->right);?//?空節(jié)點(diǎn)不入棧
????????}
????????reverse(result.begin(),?result.end());?//?將結(jié)果反轉(zhuǎn)之后就是左右中的順序了
????????return?result;
????}
};

總結(jié)

此時(shí)我們用迭代法寫出了二叉樹的前后中序遍歷，大家可以看出前序和中序是完全兩種代碼風(fēng)格，并不想遞歸寫法那樣代碼稍做調(diào)整，就可以實(shí)現(xiàn)前后中序。

這是因?yàn)榍靶虮闅v中訪問節(jié)點(diǎn)（遍歷節(jié)點(diǎn)）和處理節(jié)點(diǎn)（將元素放進(jìn)result數(shù)組中）可以同步處理，但是中序就無法做到同步！

上面這句話，可能一些同學(xué)不太理解，建議自己親手用迭代法，先寫出來前序，再試試能不能寫出中序，就能理解了。

那么問題又來了，難道 二叉樹前后中序遍歷的迭代法實(shí)現(xiàn)，就不能風(fēng)格統(tǒng)一么（即前序遍歷 改變代碼順序就可以實(shí)現(xiàn)中序 和 后序）？

當(dāng)然可以，這種寫法，還不是很好理解，我們將在下一篇文章里重點(diǎn)講解，敬請(qǐng)期待！

其他語言版本

Java：

//?前序遍歷順序：中-左-右，入棧順序：中-右-左
class?Solution?{
????public?List?preorderTraversal(TreeNode?root)?{
????????List?result?=?new?ArrayList<>();
????????if?(root?==?null){
????????????return?result;
????????}
????????Stack?stack?=?new?Stack<>();
????????stack.push(root);
????????while?(!stack.isEmpty()){
????????????TreeNode?node?=?stack.pop();
????????????result.add(node.val);
????????????if?(node.right?!=?null){
????????????????stack.push(node.right);
????????????}
????????????if?(node.left?!=?null){
????????????????stack.push(node.left);
????????????}
????????}
????????return?result;
????}
}

//?中序遍歷順序:?左-中-右?入棧順序：?左-右
class?Solution?{
????public?List?inorderTraversal(TreeNode?root)?{
????????List?result?=?new?ArrayList<>();
????????if?(root?==?null){
????????????return?result;
????????}
????????Stack?stack?=?new?Stack<>();
????????TreeNode?cur?=?root;
????????while?(cur?!=?null?||?!stack.isEmpty()){
???????????if?(cur?!=?null){
???????????????stack.push(cur);
???????????????cur?=?cur.left;
???????????}else{
???????????????cur?=?stack.pop();
???????????????result.add(cur.val);
???????????????cur?=?cur.right;
???????????}
????????}
????????return?result;
????}
}

//?后序遍歷順序?左-右-中?入棧順序：中-左-右?出棧順序：中-右-左，?最后翻轉(zhuǎn)結(jié)果
class?Solution?{
????public?List?postorderTraversal(TreeNode?root)?{
????????List?result?=?new?ArrayList<>();
????????if?(root?==?null){
????????????return?result;
????????}
????????Stack?stack?=?new?Stack<>();
????????stack.push(root);
????????while?(!stack.isEmpty()){
????????????TreeNode?node?=?stack.pop();
????????????result.add(node.val);
????????????if?(node.left?!=?null){
????????????????stack.push(node.left);
????????????}
????????????if?(node.right?!=?null){
????????????????stack.push(node.right);
????????????}
????????}
????????Collections.reverse(result);
????????return?result;
????}
}

Python：

#?前序遍歷-迭代-LC144_二叉樹的前序遍歷
class?Solution:
????def?preorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????#?根結(jié)點(diǎn)為空則返回空列表
????????if?not?root:
????????????return?[]
????????stack?=?[root]
????????result?=?[]
????????while?stack:
????????????node?=?stack.pop()
????????????#?中結(jié)點(diǎn)先處理
????????????result.append(node.val)
????????????#?右孩子先入棧
????????????if?node.right:
????????????????stack.append(node.right)
????????????#?左孩子后入棧
????????????if?node.left:
????????????????stack.append(node.left)
????????return?result
????????
#?中序遍歷-迭代-LC94_二叉樹的中序遍歷
class?Solution:
????def?inorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????if?not?root:
????????????return?[]
????????stack?=?[]??#?不能提前將root結(jié)點(diǎn)加入stack中
????????result?=?[]
????????cur?=?root
????????while?cur?or?stack:
????????????#?先迭代訪問最底層的左子樹結(jié)點(diǎn)
????????????if?cur:?????
????????????????stack.append(cur)
????????????????cur?=?cur.left??
????????????#?到達(dá)最左結(jié)點(diǎn)后處理?xiàng)ｍ斀Y(jié)點(diǎn)????
????????????else:??
????????????????cur?=?stack.pop()
????????????????result.append(cur.val)
????????????????#?取棧頂元素右結(jié)點(diǎn)
????????????????cur?=?cur.right?
????????return?result
????????
#?后序遍歷-迭代-LC145_二叉樹的后序遍歷
class?Solution:
????def?postorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????if?not?root:
????????????return?[]
????????stack?=?[root]
????????result?=?[]
????????while?stack:
????????????node?=?stack.pop()
????????????#?中結(jié)點(diǎn)先處理
????????????result.append(node.val)
????????????#?左孩子先入棧
????????????if?node.left:
????????????????stack.append(node.left)
????????????#?右孩子后入棧
????????????if?node.right:
????????????????stack.append(node.right)
????????#?將最終的數(shù)組翻轉(zhuǎn)
????????return?result[::-1]

?

?

?