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

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

前序就是ABC，父節點A在前

中序就是BAC，父節點A在中間

后序就是BCA，父節點A在最后

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

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

# 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_刷题系列 - Python用非递归实现二叉树后续遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。