今天是LeetCode專題第60篇文章，我們一起來看的是LeetCode的94題，二叉樹的中序遍歷。

這道題的官方難度是Medium，點贊3304，反對只有140，通過率有63.2%，在Medium的題目當中算是很高的了。這題非常基礎，可以說是程式設計師必會的演算法題之一。

我們先來看題意。

題意

題意很短， 只有一句話，給定一棵二叉樹，返回它中序遍歷的結果。

樣例

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

Output: [1,3,2]

用遞歸做這道題非常簡單，你能不用遞歸實現嗎？

題解

我們先來介紹一下二叉樹的中序遍歷，二叉樹有三種遍歷方式，分別是先序、中序和後序。對於初學者而言，可能會覺得這三種順序傻傻分不清楚，不知道它們之間有什麼分別。其實說白了非常簡單，遍歷方式其實指的是我們在遞歸遍歷的時候的選擇順序。

假設我們目前遞歸到的節點是u，它有左右兩個孩子。在保證左孩子一定先於右孩子訪問的前提下，我們有三種策略。第一種是先把u加入訪問序列，之後再分別遍歷左右子樹，第二種是先遞歸遍歷左子樹，然後把u加入訪問序列，最後再遍歷右子樹。第三種策略是先遞歸遍歷左右子樹，最後再把u加入訪問序列。

這三種策略之間有什麼不同呢？其實最大的不同就在於u加入訪問序列的順序不同，如果是先加入u再訪問，那麼就是先序。如果是先訪問了左子樹再來加入u，則是中序，最後如果是先遞歸了左右子樹，最後再加入u，則是後序。說白了也就是u先加入就是先序，中間加入就是中序，最後加入就是後序。如果你還覺得有點蒙的話，我們來看下程式碼就非常清晰了。

# 先序
def dfs(u):
    visited.append(u)
    dfs(u.left)
    dfs(u.right)
    
    
# 中序
def dfs(u):
    dfs(u.left)
    visited.append(u)
    dfs(u.right)
    
    
# 後序
def dfs(u):
    dfs(u.left)
    dfs(u.right)
    visited.append(u)

但是題目當中要求我們不通過遞歸來實現，這該怎麼辦呢？

其實也有辦法，我們需要從遞歸的實現原理入手。我們知道在編譯器內部，當我們從一個函數調用另外一個函數的時候，這些函數的資訊會被存儲在一個棧結構內。棧中間的每一個節點會記錄函數的名稱以及它目前運行的位置，以及一些中間變數等等。所以當我們遞歸的時候，其實就是當前的函數不停的入棧的過程。

比如我們dfs函數在第5行程式碼處遞歸調用了dfs函數，那麼編譯器內部的堆棧會記錄[(dfs, 5), (dfs, 1)]。如果我們在dfs的第一行又調用了sum函數，那麼編譯器又會把sum這個函數加入堆棧，變成：[(dfs, 5), (dfs, 1), (sum, 1)]。當函數執行完成之後，會從棧中彈出。

簡而言之，遞歸其實就是利用編譯器自行維護的棧結構來簡化我們程式碼和功能的編寫。既然這道題當中要求我們不能使用遞歸，那麼我們就只能自己來使用棧來模擬這個過程了。由於我們自己需要維護棧當中的元素，使得整個過程會稍微複雜一些。

在這道題目當中，我們使用棧來記錄樹上的節點。棧頂的節點即是當前訪問的節點。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ret = []
        stack = []
        stack.append(root)
        while len(stack) > 0:
            # 獲取棧頂頂點
            cur = stack[-1]
            if cur is None:
                stack.pop()
                continue
                
            # 如果左孩子存在，那麼優先遍歷左孩子
            if cur.left is not None:
                stack.append(cur.left)
                # 把左指針置為空，防止死循環
                # 這裡也可以用set來維護
                cur.left = None
                continue
                
            # 左邊遍歷結束之後加入序列
            ret.append(cur.val)
            stack.pop()
            if cur.right is not None:
                stack.append(cur.right)
                
        return ret

總結

如果只是二叉樹的遍歷，那這個誰都會，但如果不能使用遞歸，那麼就很考驗硬實力了。需要我們對遞歸的底層原理有深入的理解，並且熟悉棧這個數據結構的使用。這段程式碼的邏輯不難理解，但實現還是挺鍛煉人的，推薦大家試試。

今天的文章到這裡就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支援吧（關注、轉發、點贊）。

– END –