<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>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0108. 將有序數組轉換為二叉搜索樹 ## 題目地址(108. 將有序數組轉換為二叉搜索樹) <https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/> ## 題目描述 ``` <pre class="calibre18">``` 將一個按照升序排列的有序數組,轉換為一棵高度平衡二叉搜索樹。 本題中,一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。 示例: 給定有序數組: [-10,-3,0,5,9], 一個可能的答案是:[0,-3,9,-10,null,5],它可以表示下面這個高度平衡二叉搜索樹: 0 / \ -3 9 / / -10 5 ``` ``` ## 前置知識 - [二叉搜索樹](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) - [平衡二叉樹](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) - [遞歸](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - airbnb ## 思路 由于輸入是一個**升序排列的有序數組**。因此任意選擇一點,將其作為根節點,其左部分左節點,其右部分右節點即可。 因此我們很容易寫出遞歸代碼。 而題目要求是**高度平衡**的二叉搜索樹,因此我們必須要取中點。 不難證明:`由于是中點,因此左右兩部分差不會大于 1,也就是說其形成的左右子樹節點數最多相差 1,因此左右子樹高度差的絕對值不超過 1`。 形象一點來看就像你提起一根繩子,從中點提的話才能使得兩邊繩子長度相差最小。 ![](https://img.kancloud.cn/2b/af/2bafd31e4bc6d0a864a5313ad3ac267b_847x643.jpg) ## 關鍵點 - 找中點 ## 代碼 代碼支持:JS,C++,Java,Python JS Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> sortedArrayToBST = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-title">// 由于數組是排序好的,因此一個思路就是將數組分成兩半,一半是左子樹,另一半是右子樹</span> <span class="hljs-title">// 然后運用“樹的遞歸性質”遞歸完成操作即可。</span> <span class="hljs-keyword">if</span> (nums.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">null</span>; <span class="hljs-keyword">const</span> mid = nums.length >> <span class="hljs-params">1</span>; <span class="hljs-keyword">const</span> root = <span class="hljs-keyword">new</span> TreeNode(nums[mid]); root.left = sortedArrayToBST(nums.slice(<span class="hljs-params">0</span>, mid)); root.right = sortedArrayToBST(nums.slice(mid + <span class="hljs-params">1</span>)); <span class="hljs-keyword">return</span> root; }; ``` ``` Python 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">sortedArrayToBST</span><span class="hljs-params">(self, nums: List[int])</span> -> TreeNode:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums: <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span> mid = (len(nums) - <span class="hljs-params">1</span>) // <span class="hljs-params">2</span> root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid + <span class="hljs-params">1</span>:]) <span class="hljs-keyword">return</span> root ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:每次遞歸都 copy 了 N 的 空間,因此空間復雜度為 O(N2)O(N ^ 2)O(N2) 然而,實際上沒必要開辟新的空間: C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">TreeNode* <span class="hljs-title">sortedArrayToBST</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& nums)</span> </span>{ <span class="hljs-keyword">return</span> reBuild(nums, <span class="hljs-params">0</span>, nums.size()<span class="hljs-params">-1</span>); } <span class="hljs-function">TreeNode* <span class="hljs-title">reBuild</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& nums, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right)</span> </span>{ <span class="hljs-title">// 終止條件:中序遍歷為空</span> <span class="hljs-keyword">if</span>(left > right) { <span class="hljs-keyword">return</span> <span class="hljs-params">NULL</span>; } <span class="hljs-title">// 建立當前子樹的根節點</span> <span class="hljs-keyword">int</span> mid = (left+right)/<span class="hljs-params">2</span>; TreeNode * root = <span class="hljs-keyword">new</span> TreeNode(nums[mid]); <span class="hljs-title">// 左子樹的下層遞歸</span> root->left = reBuild(nums, left, mid<span class="hljs-params">-1</span>); <span class="hljs-title">// 右子樹的下層遞歸</span> root->right = reBuild(nums, mid+<span class="hljs-params">1</span>, right); <span class="hljs-title">// 返回根節點</span> <span class="hljs-keyword">return</span> root; } }; ``` ``` Java 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">public</span> TreeNode <span class="hljs-title">sortedArrayToBST</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{ <span class="hljs-keyword">return</span> dfs(nums, <span class="hljs-params">0</span>, nums.length - <span class="hljs-params">1</span>); } <span class="hljs-function"><span class="hljs-keyword">private</span> TreeNode <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> lo, <span class="hljs-keyword">int</span> hi)</span> </span>{ <span class="hljs-keyword">if</span> (lo > hi) { <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>; } <span class="hljs-keyword">int</span> mid = lo + (hi - lo) / <span class="hljs-params">2</span>; TreeNode root = <span class="hljs-keyword">new</span> TreeNode(nums[mid]); root.left = dfs(nums, lo, mid - <span class="hljs-params">1</span>); root.right = dfs(nums, mid + <span class="hljs-params">1</span>, hi); <span class="hljs-keyword">return</span> root; } } ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">sortedArrayToBST</span><span class="hljs-params">(self, nums)</span>:</span> <span class="hljs-string">""" :type nums: List[int] :rtype: TreeNode """</span> <span class="hljs-keyword">return</span> self.reBuild(nums, <span class="hljs-params">0</span>, len(nums)<span class="hljs-params">-1</span>) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reBuild</span><span class="hljs-params">(self, nums, left, right)</span>:</span> <span class="hljs-title"># 終止條件:</span> <span class="hljs-keyword">if</span> left > right: <span class="hljs-keyword">return</span> <span class="hljs-title"># 建立當前子樹的根節點</span> mid = (left + right)//<span class="hljs-params">2</span> root = TreeNode(nums[mid]) <span class="hljs-title"># 左右子樹的下層遞歸</span> root.left = self.reBuild(nums, left, mid<span class="hljs-params">-1</span>) root.right = self.reBuild(nums, mid+<span class="hljs-params">1</span>, right) <span class="hljs-keyword">return</span> root ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:隱式調用棧的開銷為 O(N)O(N)O(N) 更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 公眾號【 [力扣加加](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)】 知乎專欄【 [Lucifer - 知乎](https://www.zhihu.com/people/lu-xiao-13-70)】 點關注,不迷路!
                  <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>

                              哎呀哎呀视频在线观看