# 《構造二叉樹》專題 # 構造二叉樹系列 構造二叉樹是一個常見的二叉樹考點，相比于直接考察二叉樹的遍歷，這種題目的難度會更大。截止到目前(2020-02-08) LeetCode 關于構造二叉樹一共有三道題目，分別是： - [105. 從前序與中序遍歷序列構造二叉樹](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) - [106. 從中序與后序遍歷序列構造二叉樹](https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/) - [889. 根據前序和后序遍歷構造二叉樹](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/) 今天就讓我們用一個套路一舉攻破他們。 ## 105. 從前序與中序遍歷序列構造二叉樹 ### 題目描述 ``` <pre class="calibre18">``` 根據一棵樹的前序遍歷與中序遍歷構造二叉樹。 注意: 你可以假設樹中沒有重復的元素。 例如，給出 前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回如下的二叉樹： 3 / \ 9 20 / \ 15 7 ``` ``` ### 思路 我們以題目給出的測試用例來講解：  前序遍歷是`根左右`，因此 preorder 第一個元素一定整個樹的根。由于題目說明了沒有重復元素，因此我們可以通過 val 去 inorder 找到根在 inorder 中的索引 i。 而由于中序遍歷是`左根右`，我們容易找到 i 左邊的都是左子樹，i 右邊都是右子樹。 我使用紅色表示根，藍色表示左子樹，綠色表示右子樹。  根據此時的信息，我們能構造的樹是這樣的：  我們 preorder 繼續向后移動一位，這個時候我們得到了第二個根節點”9“，實際上就是左子樹的根節點。  我們 preorder 繼續向后移動一位，這個時候我們得到了第二個根節點”20“，實際上就是右子樹的根節點。其中右子樹由于個數大于 1，我們無法確定，我們繼續執行上述邏輯。  根據此時的信息，我們能構造的樹是這樣的：  我們不斷執行上述邏輯即可。簡單起見，遞歸的時候每次我都開辟了新的數組，這個其實是沒有必要的，我們可以通過四個變量來記錄 inorder 和 preorder 的起始位置即可。 ### 代碼 代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">buildTree</span><span class="hljs-params">(self, preorder: List[int], inorder: List[int])</span> -> TreeNode:</span> <span class="hljs-title"># 實際上inorder 和 postorder一定是同時為空的，因此你無論判斷哪個都行</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> preorder: <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span> root = TreeNode(preorder[<span class="hljs-params">0</span>]) i = inorder.index(root.val) root.left = self.buildTree(preorder[<span class="hljs-params">1</span>:i + <span class="hljs-params">1</span>], inorder[:i]) root.right = self.buildTree(preorder[i + <span class="hljs-params">1</span>:], inorder[i+<span class="hljs-params">1</span>:]) <span class="hljs-keyword">return</span> root ``` ``` **復雜度分析** - 時間復雜度：由于每次遞歸我們的 inorder 和 preorder 的總數都會減 1，因此我們要遞歸 N 次，故時間復雜度為 O(N)O(N)O(N)，其中 N 為節點個數。 - 空間復雜度：我們使用了遞歸，也就是借助了額外的棧空間來完成， 由于棧的深度為 N，因此總的空間復雜度為 O(N)O(N)O(N)，其中 N 為節點個數。 > 空間復雜度忽略了開辟數組的內存消耗。 ## 106. 從中序與后序遍歷序列構造二叉樹 如果你會了上面的題目，那么這個題目對你來說也不是難事，我們來看下。 ### 題目描述 ``` <pre class="calibre18">``` 根據一棵樹的中序遍歷與后序遍歷構造二叉樹。 注意: 你可以假設樹中沒有重復的元素。 例如，給出 中序遍歷 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: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">buildTree</span><span class="hljs-params">(self, inorder: List[int], postorder: List[int])</span> -> TreeNode:</span> <span class="hljs-title"># 實際上inorder 和 postorder一定是同時為空的，因此你無論判斷哪個都行</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> inorder: <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span> root = TreeNode(postorder[<span class="hljs-params">-1</span>]) i = inorder.index(root.val) root.left = self.buildTree(inorder[:i], postorder[:i]) root.right = self.buildTree(inorder[i+<span class="hljs-params">1</span>:], postorder[i:<span class="hljs-params">-1</span>]) <span class="hljs-keyword">return</span> root ``` ``` **復雜度分析** - 時間復雜度：由于每次遞歸我們的 inorder 和 postorder 的總數都會減 1，因此我們要遞歸 N 次，故時間復雜度為 O(N)O(N)O(N)，其中 N 為節點個數。 - 空間復雜度：我們使用了遞歸，也就是借助了額外的棧空間來完成， 由于棧的深度為 N，因此總的空間復雜度為 O(N)O(N)O(N)，其中 N 為節點個數。 > 空間復雜度忽略了開辟數組的內存消耗。 ## 889. 根據前序和后序遍歷構造二叉樹 ### 題目描述 ``` <pre class="calibre18">``` 返回與給定的前序和后序遍歷匹配的任何二叉樹。 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: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">constructFromPrePost</span><span class="hljs-params">(self, pre: List[int], post: List[int])</span> -> TreeNode:</span> <span class="hljs-title"># 實際上pre 和 post一定是同時為空的，因此你無論判斷哪個都行</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> pre: <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span> node = TreeNode(pre[<span class="hljs-params">0</span>]) <span class="hljs-keyword">if</span> len(pre) == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> node i = post.index(pre[<span class="hljs-params">1</span>]) node.left = self.constructFromPrePost(pre[<span class="hljs-params">1</span>:i + <span class="hljs-params">2</span>], post[:i + <span class="hljs-params">1</span>]) node.right = self.constructFromPrePost(pre[i + <span class="hljs-params">2</span>:], post[i + <span class="hljs-params">1</span>:<span class="hljs-params">-1</span>]) <span class="hljs-keyword">return</span> node ``` ``` **復雜度分析** - 時間復雜度：由于每次遞歸我們的 postorder 和 preorder 的總數都會減 1，因此我們要遞歸 N 次，故時間復雜度為 O(N)O(N)O(N)，其中 N 為節點個數。 - 空間復雜度：我們使用了遞歸，也就是借助了額外的棧空間來完成， 由于棧的深度為 N，因此總的空間復雜度為 O(N)O(N)O(N)，其中 N 為節點個數。 > 空間復雜度忽略了開辟數組的內存消耗。 ## 總結 如果你仔細對比一下的話，會發現我們的思路和代碼幾乎一模一樣。注意到每次遞歸我們的兩個數組個數都會減去 1，因此我們遞歸終止條件不難寫出，并且遞歸問題規模如何縮小也很容易，那就是數組總長度減去 1。 我們拿最后一個題目來說： ``` <pre class="calibre18">``` node.left = self.constructFromPrePost(pre[<span class="hljs-params">1</span>:i + <span class="hljs-params">2</span>], post[:i + <span class="hljs-params">1</span>]) node.right = self.constructFromPrePost(pre[i + <span class="hljs-params">2</span>:], post[i + <span class="hljs-params">1</span>:<span class="hljs-params">-1</span>]) ``` ``` 我們發現 pre 被拆分為兩份，pre\[1:i + 2\]和 pre\[i + 2:\]。很明顯總數少了 1，那就是 pre 的第一個元素。 也就是說如果你寫出一個，其他一個不用思考也能寫出來。 而對于 post 也一樣，post\[:i + 1\] 和 post\[i + 1:-1\]，很明顯總數少了 1，那就是 post 最后一個元素。 這個解題模板足夠簡潔，并且邏輯清晰，大家可以用我的模板試試～ ## 關注我 更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的 LeetCode 題解