1、二叉樹(shù)遍歷的遞歸算法

遞歸實(shí)現(xiàn)二叉樹(shù)的遍歷非常直觀，回顧一下遞歸的代碼：

• 前序遍歷

def preOrder(Tree node):
    if node == None:
        return
    visit(node.data)
    preOrder(node.leftchild)
    preOrder(node.rightchild)

• 中序遍歷

def inOrder(Tree node):
    if node == None:
        return 
    preOrder(node.leftchild)
    visit(node.data)
    preOrder(node.rightchild)

• 后序遍歷

def postOrder(Tree node):
    if node == None:
        return 
    preOrder(node.leftchild)
    preOrder(node.rightchild)
    visit(node.data)

他們的直觀區(qū)別僅僅在于visit(node.data)的位置或者說(shuō)順序發(fā)生了改變

2、二叉樹(shù)遍歷非遞歸算法轉(zhuǎn)化的來(lái)龍去脈

為什么要轉(zhuǎn)化為非遞歸算法

遞歸會(huì)消耗較多的?？臻g，并且不斷的函數(shù)調(diào)用和返回會(huì)消耗更多的時(shí)間

借助棧非遞歸化

遞歸，本質(zhì)上是函數(shù)幀不斷出入棧的過(guò)程。那么，我們可以直接利用棧的數(shù)據(jù)結(jié)構(gòu)來(lái)模擬遞歸的過(guò)程，轉(zhuǎn)化成非遞歸的代碼實(shí)現(xiàn)

非遞歸化的結(jié)點(diǎn)入出棧過(guò)程

入棧+出棧+訪(fǎng)問(wèn)

• 什么時(shí)候結(jié)點(diǎn)入棧
• 什么時(shí)候結(jié)點(diǎn)出棧
• 什么時(shí)候訪(fǎng)問(wèn)結(jié)點(diǎn)

要解決上面3個(gè)問(wèn)題，可以對(duì)應(yīng)遞歸形式的代碼：

• 遞歸調(diào)用導(dǎo)致當(dāng)前函數(shù)環(huán)境入棧；
• 遞歸返回導(dǎo)致棧頂?shù)暮瘮?shù)環(huán)境出棧；
• visit行是對(duì)當(dāng)前結(jié)點(diǎn)進(jìn)行訪(fǎng)問(wèn)，并不涉及任何出入棧操作。其中，訪(fǎng)問(wèn)結(jié)點(diǎn)可以是打印，也可以是將結(jié)點(diǎn)的值加入某個(gè)列表，等等

因?yàn)閷?duì)結(jié)點(diǎn)的訪(fǎng)問(wèn)和出入棧沒(méi)有關(guān)系，因此我們先忽略遞歸代碼中的visit語(yǔ)句。此時(shí)觀察三種遍歷的遞歸代碼，可以發(fā)現(xiàn)它們的結(jié)點(diǎn)出入棧順序一模一樣，重復(fù)一次，出入棧順序一模一樣

這里的代碼分析很重要！??！

def xxxOrder(Tree node):
    if node == None:
        return 
    
    # A.因?yàn)橄旅嬉M(jìn)入遞歸調(diào)用的xxxOrder(node.leftchild)，后面還得回到node的
    # 因此只要一執(zhí)行xxxOrder(node.leftchild)，node就會(huì)入棧
    xxxOrder(node.leftchild)
    # B.當(dāng)xxxOrder(node.leftchild)執(zhí)行完畢返回，即左子樹(shù)探索完了
    # 控制權(quán)自然回到結(jié)點(diǎn)node所在的這個(gè)函數(shù)體，那么結(jié)點(diǎn)node就不需要存了。所以，當(dāng)xxxOrder(node.leftchild)執(zhí)行完畢返回，node出棧
    
    # C.因?yàn)橄旅嬉M(jìn)入遞歸調(diào)用的xxxOrder(node.rightchild)，后面也還得回到node的
    # 因此只要一執(zhí)行xxxOrder(node.rightchild)，node就又會(huì)再次入棧
    xxxOrder(node.rightchild)
    # D.當(dāng)xxxOrder(node.rightchild)執(zhí)行完畢返回，即右子樹(shù)探索完畢，node出棧

可以清晰地看到，遞歸時(shí)，結(jié)點(diǎn)node要走完自己的函數(shù)體，經(jīng)歷了2次入棧出棧過(guò)程

那么，我們有必要完全模仿這樣的2次入出棧的過(guò)程嗎？當(dāng)然沒(méi)有必要
在弄清楚結(jié)點(diǎn)出入棧的過(guò)程之外，我們更要弄清楚結(jié)點(diǎn)出入棧的作用到底是什么

結(jié)點(diǎn)node入出棧的作用，很重要?。?！

• 對(duì)于前序遍歷，結(jié)點(diǎn)node在調(diào)用xxxOrder(node.leftchild)之前就被訪(fǎng)問(wèn)并入棧，在xxxOrder(node.leftchild)返回后出棧，此時(shí)node自己以及它的左子樹(shù)全部都被訪(fǎng)問(wèn)了，它的出棧僅僅是為了獲得接下來(lái)的node.rightchild。也就是說(shuō)，node的第一次出棧，是為了接下來(lái)獲得它的右孩子。這時(shí)，node沒(méi)有再次入棧的必要
• 對(duì)于中序遍歷，結(jié)點(diǎn)node在xxxOrder(node.leftchild)返回后出棧。node出棧是為了訪(fǎng)問(wèn)node本身+獲得接下來(lái)的node.rightchild，此時(shí)node的左子樹(shù)和自己本身都被訪(fǎng)問(wèn)了，在獲得node.rightchild之后，接下來(lái)的一切都和node無(wú)關(guān)。這時(shí)，node也沒(méi)有再次入棧的必要
• 對(duì)于后序遍歷，結(jié)點(diǎn)node在xxxOrder(node.leftchild)返回后出棧，是為了獲得接下來(lái)的node.rightchild；同時(shí)，結(jié)點(diǎn)node還需要再次入棧，因?yàn)樗枰趚xxOrder(node.rightchild)返回后，訪(fǎng)問(wèn)自己。因此，后序遍歷是比較特殊的

3、非遞歸形式的基礎(chǔ)代碼

基于上面分析，自然而然，非遞歸化的基本代碼就可以寫(xiě)出來(lái)了！

對(duì)于前序遍歷和中序遍歷：

def search(TreeNode):
    
    stack = list()
    
    # A.當(dāng)TreeNode不為None時(shí), 不斷入棧TreeNode
    while TreeNode != None:
        # visit(TreeNode)  # 前序
        stack.append(TreeNode)
        TreeNode = TreeNode.left
        
    # 當(dāng)棧不為空時(shí)
    while stack:
        # B.棧頂元素出棧
        top = stack.pop(-1)
        # visit(top)  # 中序
        
        # C.以top.right為根結(jié)點(diǎn)，重復(fù)ABC
        t = top.right  # 如果是多叉樹(shù)，則是 for t in top.lefted_childs:
        while t != None:
            # visit(t)  # 前序
            stack.append(t)
            t = t.left

對(duì)于后序遍歷：

def search(TreeNode):
    
    stack = list()
    last_pop_node = None
    
    # 當(dāng)TreeNode不為None時(shí), 不斷入棧TreeNode
    while TreeNode != None:
        stack.append(TreeNode)
        TreeNode = TreeNode.left
        
    # 當(dāng)棧不為空時(shí)
    while stack:
        
        # 獲取棧頂結(jié)點(diǎn)top，并判斷是否出棧
        top = stack[-1]
        t = top.right
        # 如果top無(wú)右子樹(shù) or 上一個(gè)pop的結(jié)點(diǎn)是top的右孩子，說(shuō)明top的右子樹(shù)訪(fǎng)問(wèn)完畢，出棧top并訪(fǎng)問(wèn)
        if t is None or t == last_pop_node:
            last_pop_node = stack.pop(-1)
            visit(last_pop_node)
        
        # 否則top不出棧，top的右子樹(shù)入棧
        else:
            while t != None:
                stack.append(t)
                t = t.left

例題：

給定一個(gè)二叉樹(shù)，（以層次遍歷順序的list作為輸入），返回它的 后序 遍歷
示例:
輸入: [1,null,2,3]
1
\
2
/
3

輸出: [3,2,1]

# 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]:
        result = []
        stack = list()
        last_pop_node = None
        
        # 當(dāng)root不為None時(shí), 不斷入棧root
        while root != None:
            stack.append(root)
            root = root.left
            
        # 當(dāng)棧不為空時(shí)
        while stack:
            
            # 獲取棧頂結(jié)點(diǎn)top，并判斷是否出棧
            top = stack[-1]
            t = top.right
            # 如果top無(wú)右子樹(shù)or上一個(gè)pop的結(jié)點(diǎn)是top的右孩子，說(shuō)明top的右子樹(shù)訪(fǎng)問(wèn)完畢
            if t is None or t == last_pop_node:
                last_pop_node = stack.pop(-1)
                result.append(last_pop_node.val)
            
            # 否則top不出棧，top的右子樹(shù)入棧
            else:
                while t != None:
                    stack.append(t)
                    t = t.left
        return result