DSA 後序遍歷

二叉樹的後序遍歷

後序遍歷是一種深度優先搜尋（Depth First Search），其中每個節點都以特定的順序進行訪問。 在此處 閱讀更多關於二叉樹遍歷的資訊。

對二叉樹進行後序遍歷的過程視覺化如下

後序遍歷透過遞迴地對左子樹和右子樹進行後序遍歷，然後訪問根節點來工作。 它用於刪除樹、表示式樹的字尾表示法等。

之所以稱這種遍歷為“後”序，是因為訪問節點是在遞迴呼叫左右子節點“之後”進行的。

後序遍歷的程式碼看起來是這樣的

def postOrderTraversal(node):
    if node is None:
        return
    postOrderTraversal(node.left)
    postOrderTraversal(node.right)
    print(node.data, end=", ")

postOrderTraversal() 函式將遞迴地繼續遍歷左子樹（第 4 行），直到當 C 的左子節點作為 node 引數被呼叫時，返回 None。

在 C 的左子節點返回 None 之後，第 5 行執行，C 的右子節點返回 None，然後列印字母 'C'（第 6 行）。

這意味著 C 在其左子節點和右子節點被遍歷“之後”才被訪問或列印，這就是為什麼它被稱為“後”序遍歷。

postOrderTraversal() 函式繼續傳播回先前的遞迴函式呼叫，因此下一個要列印的節點是 'D'，然後是 'A'。

該函式繼續傳播並列印節點，直到所有節點都被列印或訪問。