順便把Python用非遞歸實現二叉樹后續(xù)遍歷也寫了。

公司主營業(yè)務：網站設計制作、成都網站制作、移動網站開發(fā)等業(yè)務。幫助企業(yè)客戶真正實現互聯網宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯公司是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯公司推出衢州免費做網站回饋大家。

其實前序中序和后續(xù)都是針對父節(jié)點說的。比如下面這個最簡單二叉樹。

前序就是ABC，父節(jié)點A在前

中序就是BAC，父節(jié)點A在中間

后序就是BCA，父節(jié)點A在最后

無論多復雜二叉樹，基本都是同樣遍歷流程。

后續(xù)遍歷可以說是最簡單的，從左開始遍歷并放入棧，讀取沒有下級節(jié)點的節(jié)點值，然后把該節(jié)點推出棧，并刪除和上級節(jié)點關聯；然后替換棧中最上的點，并去遍歷右邊子節(jié)點；直到棧為空，遍歷結束。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        traversalList = []
        nodeList = []
        # travel the node, add to node stack, if the node without any sub-node, record the val; then remove it and it's link with parnet, travel back to last one in stack.
        if root != None:
            nodeList.append(root)
            while nodeList != []:
                if nodeList[-1].left != None:
                    nodeList.append(nodeList[-1].left )
                elif nodeList[-1].right != None:
                    nodeList.append(nodeList[-1].right)
                else:
                    traversalList.append(nodeList[-1].val)
                    currentNode = nodeList.pop()
                    if nodeList != []:
                        if nodeList[-1].right == currentNode:
                            nodeList[-1].right = None
                        elif nodeList[-1].left == currentNode:
                            nodeList[-1].left = None
        return traversalList

當前標題：刷題系列-Python用非遞歸實現二叉樹后續(xù)遍歷
標題網址：http://www.chinadenli.net/article44/ieocee.html

成都網站建設公司_創(chuàng)新互聯，為您提供網站設計、外貿網站建設、服務器托管、營銷型網站建設、App設計、全網營銷推廣

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯