力扣每日一題打卡 - 構(gòu)建二叉樹專題

這道題是今天（2020-09-25）力扣官方的每日一題， 之前我寫了題解，總結(jié)了?《構(gòu)建二叉樹專題》^{[1]（可以閱讀原文查看）}。有一些朋友說我的復(fù)雜度有點(diǎn)高，實(shí)際上我只是為了新手容易理解才那么寫的， 今天稍微修改一下放給大家看。

此題目和105. 從前序與中序遍歷序列構(gòu)造二叉樹^[2]?完全一致，如果你會其中一個，那么另外一個也一定會。

我們以題目給出的測試用例來講解：

后序遍歷是左右根，因此postorder最后一個元素一定整個樹的根。由于題目說明了沒有重復(fù)元素，因此我們可以通過val去inorder找到根在inorder中的索引i。而由于中序遍歷是左根右，我們?nèi)菀渍业絠左邊的都是左子樹，i右邊都是右子樹。

我使用紅色表示根，藍(lán)色表示左子樹，綠色表示右子樹。

根據(jù)此時的信息，我們能構(gòu)造的樹是這樣的：

其中右子樹由于個數(shù)大于1，我們無法確定，我們繼續(xù)執(zhí)行上述邏輯。我們postorder繼續(xù)向前移動一位，這個時候我們得到了第二個根節(jié)點(diǎn)”20“，實(shí)際上就是右子樹的根節(jié)點(diǎn)。

根據(jù)此時的信息，我們能構(gòu)造的樹是這樣的：

我們不斷執(zhí)行上述邏輯即可。

代碼：

class?Solution:
????def?buildTree(self,?inorder:?List[int],?postorder:?List[int])?->?TreeNode:
????????#?實(shí)際上inorder?和?postorder一定是同時為空的，因此你無論判斷哪個都行
????????if?not?inorder:
????????????return?None
????????root?=?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

簡單起見，遞歸的時候每次我都開辟了新的數(shù)組，這個其實(shí)是沒有必要的，我們可以通過四個變量來記錄inorder和postorder的起始位置即可， 具體見下方代碼區(qū)。

代碼

class?Solution:
????def?buildTree(self,?inorder:?List[int],?postorder:?List[int])?->?TreeNode:
????????def?dfs(inorder,?in_start,?in_end,?postorder,?post_start,?post_end):
????????????if?in_start?>?in_end:?return?None
????????????if?in_start?==?in_end:?return?TreeNode(inorder[in_start])
????????????if?post_start?==?post_end:?return?TreeNode(inorder[in_start])
????????????root?=?TreeNode(postorder[post_end])
????????????i?=?inorder.index(root.val)
????????????root.left?=?dfs(inorder,?in_start,?i?-?1,?postorder,?post_start,?post_start?+?i?-?1?-?in_start)
????????????root.right?=?dfs(inorder,?i?+?1,?in_end,?postorder,?post_start?+?i?-?1?-?in_start?+?1,?post_end?-?1)
????????????return?root
????????n?=?len(inorder)
????????return?dfs(inorder,?0,?n?-?1,?postorder,?0,?n?-?1)

「復(fù)雜度分析」

• 時間復(fù)雜度：由于每次遞歸我們的inorder和postorder的總數(shù)都會減1，因此我們要遞歸N次，故時間復(fù)雜度為?，其中N為節(jié)點(diǎn)個數(shù)。
• 空間復(fù)雜度：我們使用了遞歸，也就是借助了額外的棧空間來完成， 由于棧的深度為N，因此總的空間復(fù)雜度為?，其中N為節(jié)點(diǎn)個數(shù)。

關(guān)注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。

Reference

推薦閱讀