刷題系列 - Python用非遞歸實(shí)現(xiàn)二叉樹后續(xù)遍歷

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

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

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

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

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

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

后續(xù)遍歷可以說是最簡(jiǎn)單的，從左開始遍歷并放入棧，讀取沒有下級(jí)節(jié)點(diǎn)的節(jié)點(diǎn)值，然后把該節(jié)點(diǎn)推出棧，并刪除和上級(jí)節(jié)點(diǎn)關(guān)聯(lián)；然后替換棧中最上的點(diǎn)，并去遍歷右邊子節(jié)點(diǎn)；直到棧為空，遍歷結(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