【算法專題 】構造二叉樹系列
構造二叉樹是一個常見的二叉樹考點，相比於直接考察二叉樹的遍歷，這種題目的難度會更大。截止到目前(2020-02-08) LeetCode 關於構造二叉樹一共有三道題目，分別是：node
今天就讓咱們用一個套路一舉攻破他們。python
<!-- more -->git
105. 從前序與中序遍歷序列構造二叉樹
題目描述
根據一棵樹的前序遍歷與中序遍歷構造二叉樹。
注意:
你能夠假設樹中沒有重複的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回以下的二叉樹：
3
/ \
9 20
/ \
15 7
思路
咱們以題目給出的測試用例來說解：
github
前序遍歷是根左右，所以 preorder 第一個元素必定整個樹的根。因爲題目說明了沒有重複元素，所以咱們能夠經過 val 去 inorder 找到根在 inorder 中的索引 i。
而因爲中序遍歷是左根右，咱們容易找到 i 左邊的都是左子樹，i 右邊都是右子樹。數組
我使用紅色表示根，藍色表示左子樹，綠色表示右子樹。post
根據此時的信息，咱們能構造的樹是這樣的：測試
咱們 preorder 繼續向後移動一位，這個時候咱們獲得了第二個根節點」9「，實際上就是左子樹的根節點。ui
咱們 preorder 繼續向後移動一位，這個時候咱們獲得了第二個根節點」20「，實際上就是右子樹的根節點。其中右子樹因爲個數大於 1，咱們沒法肯定，咱們繼續執行上述邏輯。spa
根據此時的信息，咱們能構造的樹是這樣的：3d
咱們不斷執行上述邏輯便可。簡單起見，遞歸的時候每次我都開闢了新的數組，這個實際上是沒有必要的，咱們能夠經過四個變量來記錄 inorder 和 preorder 的起始位置便可。
代碼
代碼支持：Python3
Python3 Code:
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 實際上inorder 和 postorder必定是同時爲空的，所以你不管判斷哪一個都行
if not preorder:
return None
root = TreeNode(preorder[0])
i = inorder.index(root.val)
root.left = self.buildTree(preorder[1:i + 1], inorder[:i])
root.right = self.buildTree(preorder[i + 1:], inorder[i+1:])
return root
複雜度分析
- 時間複雜度：因爲每次遞歸咱們的 inorder 和 preorder 的總數都會減 1，所以咱們要遞歸 N 次，故時間複雜度爲 $O(N)$，其中 N 爲節點個數。
- 空間複雜度：咱們使用了遞歸，也就是藉助了額外的棧空間來完成， 因爲棧的深度爲 N，所以總的空間複雜度爲 $O(N)$，其中 N 爲節點個數。
空間複雜度忽略了開闢數組的內存消耗。
106. 從中序與後序遍歷序列構造二叉樹
若是你會了上面的題目，那麼這個題目對你來講也不是難事，咱們來看下。
題目描述
根據一棵樹的中序遍歷與後序遍歷構造二叉樹。
注意:
你能夠假設樹中沒有重複的元素。
例如，給出
中序遍歷 inorder = [9,3,15,20,7]
後序遍歷 postorder = [9,15,7,20,3]
返回以下的二叉樹：
3
/ \
9 20
/ \
15 7
思路
咱們以題目給出的測試用例來說解：
後序遍歷是左右根，所以 postorder 最後一個元素必定整個樹的根。因爲題目說明了沒有重複元素，所以咱們能夠經過 val 去 inorder 找到根在 inorder 中的索引 i。
而因爲中序遍歷是左根右，咱們容易找到 i 左邊的都是左子樹，i 右邊都是右子樹。
我使用紅色表示根，藍色表示左子樹，綠色表示右子樹。
根據此時的信息，咱們能構造的樹是這樣的：
其中右子樹因爲個數大於 1，咱們沒法肯定，咱們繼續執行上述邏輯。咱們 postorder 繼續向前移動一位，這個時候咱們獲得了第二個根節點」20「，實際上就是右子樹的根節點。
根據此時的信息，咱們能構造的樹是這樣的：
咱們不斷執行上述邏輯便可。簡單起見，遞歸的時候每次我都開闢了新的數組，這個實際上是沒有必要的，咱們能夠經過四個變量來記錄 inorder 和 postorder 的起始位置便可。
代碼
代碼支持：Python3
Python3 Code:
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
# 實際上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
複雜度分析
- 時間複雜度：因爲每次遞歸咱們的 inorder 和 postorder 的總數都會減 1，所以咱們要遞歸 N 次，故時間複雜度爲 $O(N)$，其中 N 爲節點個數。
- 空間複雜度：咱們使用了遞歸，也就是藉助了額外的棧空間來完成， 因爲棧的深度爲 N，所以總的空間複雜度爲 $O(N)$，其中 N 爲節點個數。
空間複雜度忽略了開闢數組的內存消耗。
889. 根據前序和後序遍歷構造二叉樹
題目描述
返回與給定的前序和後序遍歷匹配的任何二叉樹。 pre 和 post 遍歷中的值是不一樣的正整數。 示例： 輸入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] 輸出：[1,2,3,4,5,6,7] 提示： 1 <= pre.length == post.length <= 30 pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列 每一個輸入保證至少有一個答案。若是有多個答案，能夠返回其中一個。
思路
咱們以題目給出的測試用例來說解：
前序遍歷是根左右，所以 preorder 第一個元素必定整個樹的根，preorder 第二個元素（若是存在的話）必定是左子樹。因爲題目說明了沒有重複元素，所以咱們能夠經過 val 去 postorder 找到 pre[1]在 postorder 中的索引 i。
而因爲後序遍歷是左右根，所以咱們容易得出。 postorder 中的 0 到 i(包含)是左子樹，preorder 的 1 到 i+1（包含）也是左子樹。
其餘部分能夠參考上面兩題。
代碼
代碼支持：Python3
Python3 Code:
class Solution:
def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
# 實際上pre 和 post必定是同時爲空的，所以你不管判斷哪一個都行
if not pre:
return None
node = TreeNode(pre[0])
if len(pre) == 1:
return node
i = post.index(pre[1])
node.left = self.constructFromPrePost(pre[1:i + 2], post[:i + 1])
node.right = self.constructFromPrePost(pre[i + 2:], post[i + 1:-1])
return node
複雜度分析
- 時間複雜度：因爲每次遞歸咱們的 postorder 和 preorder 的總數都會減 1，所以咱們要遞歸 N 次，故時間複雜度爲 $O(N)$，其中 N 爲節點個數。
- 空間複雜度：咱們使用了遞歸，也就是藉助了額外的棧空間來完成， 因爲棧的深度爲 N，所以總的空間複雜度爲 $O(N)$，其中 N 爲節點個數。
空間複雜度忽略了開闢數組的內存消耗。
總結
若是你仔細對比一下的話，會發現咱們的思路和代碼幾乎如出一轍。注意到每次遞歸咱們的兩個數組個數都會減去 1，所以咱們遞歸終止條件不難寫出，而且遞歸問題規模如何縮小也很容易，那就是數組總長度減去 1。
咱們拿最後一個題目來講：
node.left = self.constructFromPrePost(pre[1:i + 2], post[:i + 1]) node.right = self.constructFromPrePost(pre[i + 2:], post[i + 1:-1])
咱們發現 pre 被拆分爲兩份，pre[1:i + 2]和 pre[i + 2:]。很明顯總數少了 1，那就是 pre 的第一個元素。 也就是說若是你寫出一個，其餘一個不用思考也能寫出來。
而對於 post 也同樣，post[:i + 1] 和 post[i + 1:-1]，很明顯總數少了 1，那就是 post 最後一個元素。
這個解題模板足夠簡潔，而且邏輯清晰，你們能夠用個人模板試試～
關注我
更多題解能夠訪問個人 LeetCode 題解倉庫：https://github.com/azl3979858... 。 目前已經 30K star 啦。
你們也能夠關注個人公衆號《力扣加加》獲取更多更新鮮的 LeetCode 題解
