先序和中序遍曆序列確定一顆二叉樹（還原二叉樹）

我用了兩種方法解，分別是遞歸法和堆棧法。遞歸法是最簡單的，學完遞歸法後，建議一定要學習堆棧法，因為遞歸程序實際上也是堆棧實現的。

    分析：        

• 先根據線序遍曆序列確定根結點，即第一個結點（根左右）。
• 根據根節點再中序遍曆序列中分別分割出左子樹和右子樹（左根右：根節點左側為左子樹，右側為右子樹）。
• 對左子樹和右子樹分別遞歸使用相同的方法繼續分解

    例：

        先序序列  a bcde fghij ;

        中序序列 cbed a hgijf

        對於根節點a，先序、中序序列可以分別分解為下圖兩棵樹：

          對於每個節點的左子樹、右子樹，按照同樣的算法逐步分解，最後可以確認一棵唯一樹。

一、遞歸法       

遞歸代碼實現如下（Python3）： 每次遞歸都能根據先序、中序序列確認一棵唯一樹。

def buildTree(preorder:str, inorder:str):
    """
    根據前序，中序，確認唯一樹
    preorder: 先序序列
    inorder: 中序序列
    """
    if not preorder:
        return None
    
    # 構造當前序列“根”節點
    p = T = BinTreeNode()  
    p.value = preorder[0]
    index = inorder.find(p.value)
    if index == -1:
        print("非法樹")
    l_in = inorder[:index]  # 中序序列左子樹
    r_in = inorder[index+1:]  # 中序序列右子樹
    l_pre = preorder[1:len(l_in)+1]  # 先序序列左子樹
    r_pre = preorder[len(l_in)+1:]  # 先序序列右子樹

    # 構造當前序列左、右子樹
    p.left = buildTree(l_pre, l_in)  
    p.right = buildTree(r_pre, r_in)

    return T



T = buildTree("abcdefghij", "cbedahgijf")

二、堆棧法

        實現遞歸算法後，雖然簡單，而且代碼邏輯清晰，但是效率太低了。我們知道，遞歸實際上就是利用棧實現的，那麼我們同樣可以利用這個原理來做。

        分析：       

1.   首先一直構造樹的最左子樹，直到沒有左子樹，每遇到一個結點就放進棧頂；
2.   返回上一個結點（從棧頂彈出一個元素），構造其右子樹；
3.   返回第一步，直到棧為空，所有結點構造完畢。

說明：為什麼是棧呢？因為構造完左子樹，我們需要回退到上一步構造右子樹，即知道當前結點的父親是誰，或者知道當前結點的右兄弟是誰，棧的後進先出性質就很適合用來保存“上一步”。遞歸也是利用這個原理。

       

具體步驟圖解如下：

        第一步：構造左子樹，直到左子樹為空（^），此時棧內有【a , b, c

         第二步：回到上一步（c），構造其右子樹，右子樹為空，彈出棧頂元素（b）。

        第三步：當前結點是b，繼續構造右子樹。

        第四步：回到第一步，構造當前結點（d）的左子樹，直到左子樹為空。如此循環，當根節點左子樹構造完成後，狀態如下：

        右子樹同理。

代碼實現：

def buildTree3(preorder:str, inorder:str):
    """
    根據前序，中序，確認唯一樹
    """
    if not preorder:
        return None

    # 樹根
    p = T = BinTreeNode()
    s = ArrStack()

    p.value = preorder[0]

    preo = preorder[1: inorder.find(p.value)+1]
    inord = inorder[: inorder.find(p.value)]
    
    # 根結點、右子樹序列入棧
    s.push((p, preorder[inorder.find(p.value)+1:], inorder[inorder.find(p.value)+1:]))  
    
    while(p or (not s.isEmpty())):
        if (preo):  # 左子樹序列不為空，一直構造左子樹
            t = BinTreeNode()
            t.value = preo[0]
            p.left = t
            p = p.left

        else:
            # 沒有左子樹了, 彈出一個棧頂結點, 轉到右子樹
            p, preo, inord = s.pop()
            if not preo:  # 右子樹序列為空，跳過
                p = p.right
                continue

            # 右子樹序列不為空，繼續構造
            t = BinTreeNode()
            t.value = preo[0]
            p.right = t
            p = p.right

        # 分別找到左右子樹
        i = inord.find(preo[0])
        lino = inord[:i]  # 中序遍曆左子樹
        rino = inord[i + 1:]  # 中序遍曆右子樹
        lpreo = preo[1:len(lino) + 1]  # 先序遍曆左子樹
        rpreo = preo[len(lino) + 1:]  # 先序遍曆右子樹

        # 下一層左子樹
        preo = lpreo
        inord = lino

        # 記住自己，以及兩個序列的右子樹
        if p:
            s.push((p, rpreo, rino))  # 記住自己或者記住右子樹

    return T

三、效率對比

調用 

 效率比大概是5-6倍。

四、總結

        通過這個練習，可以充分鍛煉到遞歸、堆棧的思想。