105. 從前序與中序遍歷序列構(gòu)造二叉樹(shù)

根據(jù)一棵樹(shù)的前序遍歷與中序遍歷構(gòu)造二叉樹(shù)。

注意:

你可以假設(shè)樹(shù)中沒(méi)有重復(fù)的元素。

例如，給出

前序遍歷 preorder = [3,9,20,15,7]

中序遍歷 inorder = [9,3,15,20,7]

返回如下的二叉樹(shù)：

? ? 3

? ?/ \

? 9? 20

? ? /? \

? ?15? ?7

題目解析

題目解答

對(duì)于任意一顆樹(shù)而言，前序遍歷的形式總是

[ 根節(jié)點(diǎn), [左子樹(shù)的前序遍歷結(jié)果], [右子樹(shù)的前序遍歷結(jié)果] ]

即根節(jié)點(diǎn)總是前序遍歷中的第一個(gè)節(jié)點(diǎn)。而中序遍歷的形式總是

[ [左子樹(shù)的中序遍歷結(jié)果], 根節(jié)點(diǎn), [右子樹(shù)的中序遍歷結(jié)果] ]

只要我們?cè)谥行虮闅v中定位到根節(jié)點(diǎn)，那么我們就可以分別知道左子樹(shù)和右子樹(shù)中的節(jié)點(diǎn)數(shù)目。由于同一顆子樹(shù)的前序遍歷和中序遍歷的長(zhǎng)度顯然是相同的，因此我們就可以對(duì)應(yīng)到前序遍歷的結(jié)果中，對(duì)上述形式中的所有左右括號(hào)進(jìn)行定位。

這樣以來(lái)，我們就知道了左子樹(shù)的前序遍歷和中序遍歷結(jié)果，以及右子樹(shù)的前序遍歷和中序遍歷結(jié)果，我們就可以遞歸地對(duì)構(gòu)造出左子樹(shù)和右子樹(shù)，再將這兩顆子樹(shù)接到根節(jié)點(diǎn)的左右位置。

代碼展示

# 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, preorder: List[int], inorder: List[int]) -> TreeNode:        # step 1 : 判空        if not preorder or not inorder:             return        # step 2：以 前序遍歷 第一個(gè)點(diǎn) 作為 根        root = TreeNode(preorder[0])         # step 3：獲取根節(jié)點(diǎn) 在 中序遍歷 中的位置        idx = inorder.index(preorder[0])         # step 4：構(gòu)建左子樹(shù)        root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx])        # step 5：構(gòu)建右子樹(shù)        root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:])        return root

復(fù)雜度計(jì)算

• 時(shí)間復(fù)雜度 O(N)：當(dāng)樹(shù)退化為鏈表時(shí)（全部為右子節(jié)點(diǎn)），無(wú)論 k 的值大小，遞歸深度都為 N ，占用 O(N) 時(shí)間。

• 空間復(fù)雜度 O(N) ：當(dāng)樹(shù)退化為鏈表時(shí)（全部為右子節(jié)點(diǎn)），系統(tǒng)使用 O(N)大小的?？臻g。

運(yùn)行結(jié)果