如果只是前中后序遍歷的其中一種，是不可能唯一確定一個二叉樹的，必須是其中兩個的結合，由此便產生了三道題目，在這里可以全部秒殺。
需要記住的要點是：
前序（根左右）——第一個節點一定是根節點；
中序（左根右）——根節點左邊一定是左子樹，右邊一定是右子樹；
后序（左右根）——最后一個節點一定是根節點。

樹節點類定義如下：

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right

105. 從前序與中序遍歷序列構造二叉樹

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:if not preorder: # 判斷空樹return Noneroot = TreeNode(preorder[0]) # 根節點i = inorder.index(root.val) # 根節點下標為 i，左子樹長度也已知為 iroot.left = self.buildTree(preorder[1:i+1], inorder[:i]) # 左子樹root.right = self.buildTree(preorder[i+1:], inorder[i+1:]) # 右子樹return root

從前序找到根節點，然后找到其在中序的位置 i，則該位置的左邊 [:i] 為左子樹，右邊 [i+1:] 為右子樹。因為已知左子樹的長度為 i，則前序中的左子樹為 [1:i+1]，右子樹為 [i+1:]。

優化的寫法是，遞歸的時候傳入指針而不是傳入整個列表，所以列表不變而指針變，左子樹的長度是兩個指針之差：

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):if preorder_left > preorder_right: # 判斷空樹return Noneroot = TreeNode(preorder[preorder_left]) # 根節點inorder_root = inorder.index(root.val) # 根節點下標size_left_subtree = inorder_root - inorder_left # 左子樹長度root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1) # 左子樹root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right) # 右子樹return rootn = len(preorder)return myBuildTree(0, n - 1, 0, n - 1)

更加優化的寫法，是用一個字典（哈希映射）記錄下中序列表中數值與下標位置的關系，方便快速找到根的位置：

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):if preorder_left > preorder_right: # 判斷空樹return Noneroot = TreeNode(preorder[preorder_left]) # 根節點inorder_root = index[root.val] # 根節點下標size_left_subtree = inorder_root - inorder_left # 左子樹長度root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1) # 左子樹root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right) # 右子樹return rootn = len(preorder)# 構造哈希映射，幫助我們快速定位根節點index = {element: i for i, element in enumerate(inorder)}return myBuildTree(0, n - 1, 0, n - 1)

106. 從中序與后序遍歷序列構造二叉樹

class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:if not inorder: # 判斷空樹return Noneroot = TreeNode(postorder[-1])i = inorder.index(root.val)root.left = self.buildTree(inorder[:i], postorder[:i])root.right = self.buildTree(inorder[i+1:], postorder[i:-1])return root

從后序找到根節點，然后找到其在中序的位置 i，則該位置的左邊 [:i] 為左子樹，右邊 [i+1:] 為右子樹。因為已知左子樹的長度為 i，則后序中的左子樹為 [:i]，右子樹為 [i:]。優化寫法如下：

class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:def mybuildTree(inorder_left:int, inorder_right:int, postorder_left:int, postorder_right:int):if inorder_left > inorder_right: # 判斷空樹return Noneroot = TreeNode(postorder[postorder_right]) # 根節點inorder_root = index[root.val]size_left_subtree = inorder_root - inorder_left # 左子樹長度root.left = mybuildTree(inorder_left, inorder_root - 1, postorder_left, postorder_left + size_left_subtree - 1) # 左子樹root.right = mybuildTree(inorder_root + 1, inorder_right, postorder_left + size_left_subtree, postorder_right - 1) # 右子樹return rootn = len(inorder)# 構造哈希映射，幫助我們快速定位根節點index = {element: i for i, element in enumerate(inorder)}return mybuildTree(0, n-1, 0, n-1)

889. 根據前序和后序遍歷構造二叉樹

class Solution:def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:if not preorder: # 判斷空樹return Noneroot = TreeNode(preorder[0])if len(preorder) == 1: # 下面用到了pre[1]，則必須確保長度大于1return rooti = postorder.index(preorder[1])root.left = self.constructFromPrePost(preorder[1:i+2], postorder[:i+1])root.right = self.constructFromPrePost(preorder[i+2:], postorder[i+1:-1])return root

從前序找到根節點，可知其下一個節點是左子節點（左子樹的根節點），在后序中找到其位置 i，則該位置的左邊 [:i+1] 為左子樹，右邊 [i+1:] 為右子樹。因為已知左子樹的長度為 i，則前序中的左子樹為 [1:i+2]，右子樹為 [i+2:-1]。注意一個知識點：前序和后序不能唯一確定一棵二叉樹，因為沒有中序遍歷無法確定左右部分，也就是無法分割。優化寫法如下：

class Solution:def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:def myconstruct(preorder_left, preorder_right, postorder_left, postorder_right):if preorder_left > preorder_right:return Noneroot = TreeNode(preorder[preorder_left])if preorder_left == preorder_right:return rootpostorder_left_root = index[preorder[preorder_left+1]]size_left_subtree = postorder_left_root - postorder_leftroot.left = myconstruct(preorder_left + 1, preorder_left + size_left_subtree + 1, postorder_left,postorder_left + size_left_subtree)root.right = myconstruct(preorder_left + size_left_subtree + 2, preorder_right, postorder_left + size_left_subtree + 1, postorder_right - 1)return rootn = len(preorder)index = {element: i for i, element in enumerate(postorder)}return myconstruct(0, n-1, 0, n-1)

總結：三道題的關鍵，就是從前序或者后序遍歷找到根節點，然后使用根節點或者根節點的左子節點來區分左右子樹，完成遞歸。可以注意到，遞歸的時候：preorder 肯定沒有第一個（根節點），inorder肯定沒有第 i 個，postorder肯定沒有最后一個；然后根據區分左右子樹時用的是根節點還是它的左子節點，決定是 i 還是 i + 1。

總結

以上是生活随笔為你收集整理的从前中后序遍历构造二叉树，三题无脑秒杀的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。