假期繼續(xù)刷題，也沒有別的什么事情可以干。

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名申請、虛擬空間、營銷軟件、網(wǎng)站建設、華亭網(wǎng)站維護、網(wǎng)站推廣。

這個題是給出中序和后序遍歷隊列，構造對應二叉樹；題目很簡單，如下圖，給出兩個遍歷隊列，構成二叉樹，這里假定沒有重復點。

 

想了好幾天，真是慚愧，因為一直想一次遍歷就完成構造，最后發(fā)現(xiàn)不行；然后就硬搞出一個多重循環(huán)的遍歷方法，雖然可行，但是提交后提示耗時超過限制。最后還是用遞歸實現(xiàn)的。

其實原理很簡單，對于后續(xù)遍歷隊列，最后一個值就是整個二叉樹的根節(jié)點；而這個根節(jié)點去掉后，可以把二叉樹分成左右兩個樹，在中序隊列中，按照這個根節(jié)點來拆分出可以得到左右隊列，分布對應左邊樹和右邊樹的所有點。而且其實后序隊列也是按照左右樹節(jié)點劃分的，只要知道左右樹的節(jié)點數(shù)量，來劃分就可以了，這個可以從中序隊列劃分結果獲得。反復同理，再劃分出來左右樹繼續(xù)劃分，可以得到葉子節(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 buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if inorder == []:
            return None
        else:
            if len(inorder) == 1:
                return TreeNode(inorder[0])
            else:
                RootVal = postorder[-1]
                currentNode = TreeNode(RootVal)
                inorderLeft = inorder[:inorder.index(RootVal)]
                inorderRight = inorder[inorder.index(RootVal)+1:]
                postorder.pop()
                postorderLeft = postorder[:len(inorderLeft)]
                postorderRight = postorder[-len(inorderRight):] 
                currentNode.left = self.buildTree(inorderLeft,postorderLeft)
                currentNode.right = self.buildTree(inorderRight,postorderRight)
                return currentNode

  

分享標題：刷題系列-中序和后序遍歷隊列，構造對應二叉樹；-創(chuàng)新互聯(lián)
文章源于：http://weahome.cn/article/ddshss.html