如何分析python二叉樹非遞歸版后序遍歷

今天就跟大家聊聊有關如何分析python二叉樹非遞歸版后序遍歷，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

二叉樹的非遞歸版后序遍歷，首先定義TreeNode如下：

"""

TreeNode class

"""

class TreeNode(object):

    #constructor

    def __init__(self, val):

        self.val = val

        self.right = None

        self.left = None

    val = 0

    right = None

    left = None

非遞歸后序遍歷思路：

cur指針指向當前正遍歷到的節點，如果，

滿足情況1：不為None，且左孩子不為None，則沿著左側一直遍歷，直到不滿足條件；

如不滿足情況1，說明要么cur為None,或者左孩子為None，不管哪種情況，都先拿出stack中的最后一個元素，又細分為兩種情況：

1. cur的右孩子不為None，且未訪問過，則伸向cur的右子樹遍歷

2. 若不滿足（要么cur沒有右孩子，要么右孩子訪問過），不論哪種情況，都要訪問cur節點了，訪問后出棧，標記它為訪問過，同時當前訪問的元素置為None。

python代碼實現如下：

"""

post order using stack for binary tree

"""

def postOrderUsingStack(node=None):

    visits=[]

    stack = []

    if node is None:

        return

    stack.append(node)

    cur = node

    visited=None

    while len(stack)>0:

        if cur is not None and cur.left is not None:

            stack.append(cur.left)

            cur = cur.left

        else:

            cur =stack[-1]

            # right child for current node is not None and is not visited

            if cur.right is not None and cur.right!=visited:

                cur=cur.right

                stack.append(cur)

            else:

                # do a visit

                visits.append(cur.val)

                stack.pop()

                visited = cur

                cur=None

    return visits

單測試如下：

root = TreeNode(1)

root.left=TreeNode(2)

root.left.left = TreeNode(4)

root.right = TreeNode(3)

vals = postOrderUsingStack(root)

print(vals)

后序遍歷的結果如下：

看完上述內容，你們對如何分析python二叉樹非遞歸版后序遍歷有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。