<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 《構造二叉樹》專題 # 構造二叉樹系列 構造二叉樹是一個常見的二叉樹考點,相比于直接考察二叉樹的遍歷,這種題目的難度會更大。截止到目前(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 ``` ``` ### 思路 我們以題目給出的測試用例來講解: ![](https://img.kancloud.cn/3f/d9/3fd97e1a73d677b734ff6834f2071d04_1142x490.jpg) 前序遍歷是`根左右`,因此 preorder 第一個元素一定整個樹的根。由于題目說明了沒有重復元素,因此我們可以通過 val 去 inorder 找到根在 inorder 中的索引 i。 而由于中序遍歷是`左根右`,我們容易找到 i 左邊的都是左子樹,i 右邊都是右子樹。 我使用紅色表示根,藍色表示左子樹,綠色表示右子樹。 ![](https://img.kancloud.cn/58/b5/58b5a76546087f1a924443b276663f2a_1116x444.jpg) 根據此時的信息,我們能構造的樹是這樣的: ![](https://img.kancloud.cn/71/93/719358d994f4c4ec0a1e79c4a0435f47_1226x414.jpg) 我們 preorder 繼續向后移動一位,這個時候我們得到了第二個根節點”9“,實際上就是左子樹的根節點。 ![](https://img.kancloud.cn/90/9f/909feff5a8dd8ef7089865723f82e028_1108x452.jpg) 我們 preorder 繼續向后移動一位,這個時候我們得到了第二個根節點”20“,實際上就是右子樹的根節點。其中右子樹由于個數大于 1,我們無法確定,我們繼續執行上述邏輯。 ![](https://img.kancloud.cn/cd/a4/cda4a47c51509fc9ba3c2da86f1a8537_1344x474.jpg) 根據此時的信息,我們能構造的樹是這樣的: ![](https://img.kancloud.cn/4f/4a/4f4a37ff5601a634807d5f49b122d80c_1144x642.jpg) 我們不斷執行上述邏輯即可。簡單起見,遞歸的時候每次我都開辟了新的數組,這個其實是沒有必要的,我們可以通過四個變量來記錄 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 ``` ``` ### 思路 我們以題目給出的測試用例來講解: ![](https://img.kancloud.cn/4b/8d/4b8d2cc9be7a57e838ec740e62d8ddd9_1050x452.jpg) 后序遍歷是`左右根`,因此 postorder 最后一個元素一定整個樹的根。由于題目說明了沒有重復元素,因此我們可以通過 val 去 inorder 找到根在 inorder 中的索引 i。 而由于中序遍歷是`左根右`,我們容易找到 i 左邊的都是左子樹,i 右邊都是右子樹。 我使用紅色表示根,藍色表示左子樹,綠色表示右子樹。 ![](https://img.kancloud.cn/07/ba/07ba82aadc2eb45d71dfb4e0653324f1_1196x484.jpg) 根據此時的信息,我們能構造的樹是這樣的: ![](https://img.kancloud.cn/71/93/719358d994f4c4ec0a1e79c4a0435f47_1226x414.jpg) 其中右子樹由于個數大于 1,我們無法確定,我們繼續執行上述邏輯。我們 postorder 繼續向前移動一位,這個時候我們得到了第二個根節點”20“,實際上就是右子樹的根節點。 ![](https://img.kancloud.cn/d0/03/d003b54dbfbb746dff754fd193dc1d40_1204x496.jpg) 根據此時的信息,我們能構造的樹是這樣的: ![](https://img.kancloud.cn/4f/4a/4f4a37ff5601a634807d5f49b122d80c_1144x642.jpg) 我們不斷執行上述邏輯即可。簡單起見,遞歸的時候每次我都開辟了新的數組,這個其實是沒有必要的,我們可以通過四個變量來記錄 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 的排列 每個輸入保證至少有一個答案。如果有多個答案,可以返回其中一個。 ``` ``` ### 思路 我們以題目給出的測試用例來講解: ![](https://img.kancloud.cn/3f/d9/3fd97e1a73d677b734ff6834f2071d04_1142x490.jpg) 前序遍歷是`根左右`,因此 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 題解 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看