聽說遞歸能做的，棧也能做！
本文轉載自微信公眾號「代碼隨想錄」，作者程序員Carl 。轉載本文請聯系代碼隨想錄公眾號。
二叉樹的迭代遍歷
看完本篇大家可以使用迭代法，再重新解決如下三道leetcode上的題目：
- 144.二叉樹的前序遍歷
- 94.二叉樹的中序遍歷
- 145.二叉樹的后序遍歷
為什么可以用迭代法(非遞歸的方式)來實現二叉樹的前后中序遍歷呢?
我們在棧與隊列：匹配問題都是棧的強項中提到了，遞歸的實現就是：每一次遞歸調用都會把函數的局部變量、參數值和返回地址等壓入調用棧中，然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數，所以這就是遞歸為什么可以返回上一層位置的原因。
此時大家應該知道我們用棧也可以是實現二叉樹的前后中序遍歷了。
前序遍歷(迭代法)
我們先看一下前序遍歷。
前序遍歷是中左右，每次先處理的是中間節點，那么先將跟節點放入棧中，然后將右孩子加入棧，再加入左孩子。
為什么要先加入 右孩子，再加入左孩子呢?因為這樣出棧的時候才是中左右的順序。
動畫如下：
不難寫出如下代碼: (注意代碼中空節點不入棧)
- class Solution {
- public:
- vector<int> preorderTraversal(TreeNode* root) {
- stack<TreeNode*> st;
- vector<int> 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); // 右（空節點不入棧）
- if (node->left) st.push(node->left); // 左（空節點不入棧）
- }
- return result;
- }
- };
此時會發現貌似使用迭代法寫出前序遍歷并不難，確實不難。
此時是不是想改一點前序遍歷代碼順序就把中序遍歷搞出來了?
其實還真不行!
但接下來，再用迭代法寫中序遍歷的時候，會發現套路又不一樣了，目前的前序遍歷的邏輯無法直接應用到中序遍歷上。
中序遍歷(迭代法)
為了解釋清楚，我說明一下 剛剛在迭代的過程中，其實我們有兩個操作：
處理：將元素放進result數組中
訪問：遍歷節點
分析一下為什么剛剛寫的前序遍歷的代碼，不能和中序遍歷通用呢，因為前序遍歷的順序是中左右，先訪問的元素是中間節點，要處理的元素也是中間節點，所以剛剛才能寫出相對簡潔的代碼，因為要訪問的元素和要處理的元素順序是一致的，都是中間節點。
那么再看看中序遍歷，中序遍歷是左中右，先訪問的是二叉樹頂部的節點，然后一層一層向下訪問，直到到達樹左面的最底部，再開始處理節點(也就是在把節點的數值放進result數組中)，這就造成了處理順序和訪問順序是不一致的。
那么在使用迭代法寫中序遍歷，就需要借用指針的遍歷來幫助訪問節點，棧則用來處理節點上的元素。
動畫如下：
中序遍歷，可以寫出如下代碼：
- class Solution {
- public:
- vector<int> inorderTraversal(TreeNode* root) {
- vector<int> result;
- stack<TreeNode*> st;
- TreeNode* cur = root;
- while (cur != NULL || !st.empty()) {
- if (cur != NULL) { // 指針來訪問節點，訪問到最底層
- st.push(cur); // 將訪問的節點放進棧
- cur = cur->left; // 左
- } else {
- cur = st.top(); // 從棧里彈出的數據，就是要處理的數據（放進result數組里的數據）
- st.pop();
- result.push_back(cur->val); // 中
- cur = cur->right; // 右
- }
- }
- return result;
- }
- };
后序遍歷(迭代法)
再來看后序遍歷，先序遍歷是中左右，后續遍歷是左右中，那么我們只需要調整一下先序遍歷的代碼順序，就變成中右左的遍歷順序，然后在反轉result數組，輸出的結果順序就是左右中了，如下圖：
所以后序遍歷只需要前序遍歷的代碼稍作修改就可以了，代碼如下：
- class Solution {
- public:
- vector<int> postorderTraversal(TreeNode* root) {
- stack<TreeNode*> st;
- vector<int> 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); // 相對于前序遍歷，這更改一下入棧順序 （空節點不入棧）
- if (node->right) st.push(node->right); // 空節點不入棧
- }
- reverse(result.begin(), result.end()); // 將結果反轉之后就是左右中的順序了
- return result;
- }
- };
總結
此時我們用迭代法寫出了二叉樹的前后中序遍歷，大家可以看出前序和中序是完全兩種代碼風格，并不想遞歸寫法那樣代碼稍做調整，就可以實現前后中序。
這是因為前序遍歷中訪問節點(遍歷節點)和處理節點(將元素放進result數組中)可以同步處理，但是中序就無法做到同步!
上面這句話，可能一些同學不太理解，建議自己親手用迭代法，先寫出來前序，再試試能不能寫出中序，就能理解了。
那么問題又來了，難道 二叉樹前后中序遍歷的迭代法實現，就不能風格統一么(即前序遍歷 改變代碼順序就可以實現中序 和 后序)?
當然可以，這種寫法，還不是很好理解，我們將在下一篇文章里重點講解，敬請期待!
其他語言版本
Java：
- // 前序遍歷順序：中-左-右，入棧順序：中-右-左
- class Solution {
- public List<Integer> preorderTraversal(TreeNode root) {
- List<Integer> result = new ArrayList<>();
- if (root == null){
- return result;
- }
- Stack<TreeNode> 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<Integer> inorderTraversal(TreeNode root) {
- List<Integer> result = new ArrayList<>();
- if (root == null){
- return result;
- }
- Stack<TreeNode> 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;
- }
- }
- // 后序遍歷順序 左-右-中 入棧順序：中-左-右 出棧順序：中-右-左， 最后翻轉結果
- class Solution {
- public List<Integer> postorderTraversal(TreeNode root) {
- List<Integer> result = new ArrayList<>();
- if (root == null){
- return result;
- }
- Stack<TreeNode> 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]:
- # 根結點為空則返回空列表
- if not root:
- return []
- stack = [root]
- result = []
- while stack:
- node = stack.pop()
- # 中結點先處理
- 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結點加入stack中
- result = []
- cur = root
- while cur or stack:
- # 先迭代訪問最底層的左子樹結點
- if cur:
- stack.append(cur)
- cur = cur.left
- # 到達最左結點后處理棧頂結點
- else:
- cur = stack.pop()
- result.append(cur.val)
- # 取棧頂元素右結點
- 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()
- # 中結點先處理
- result.append(node.val)
- # 左孩子先入棧
- if node.left:
- stack.append(node.left)
- # 右孩子后入棧
- if node.right:
- stack.append(node.right)
- # 將最終的數組翻轉
- return result[::-1]
