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

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 面試題 17.12. BiNode # 題目地址(面試題 17.12. BiNode) <https://leetcode-cn.com/problems/binode-lcci/> ## 題目描述 ``` <pre class="calibre18">``` 二叉樹數據結構TreeNode可用來表示單向鏈表(其中left置空,right為下一個鏈表節點)。實現一個方法,把二叉搜索樹轉換為單向鏈表,要求依然符合二叉搜索樹的性質,轉換操作應是原址的,也就是在原始的二叉搜索樹上直接修改。 返回轉換后的單向鏈表的頭節點。 注意:本題相對原題稍作改動 示例: 輸入: [4,2,5,1,3,null,6,0] 輸出: [0,null,1,null,2,null,3,null,4,null,5,null,6] 提示: 節點數量不會超過 100000。 ``` ``` ## 前置知識 - 二叉查找樹 - 遞歸 - [二叉樹的遍歷](binary-tree-traversal.html) ## 公司 - 暫無 ## 思路 實際上這就是一個考察二叉樹遍歷 + 二叉查找樹性質的題目。需要注意的是指針操作,這一點和鏈表反轉系列題目是一樣的。 首先我們要知道一個性質: 對于一個二叉查找樹來說,其中序遍歷結果是一個有序數組。 而題目要求你輸出的恰好就是有序數組(雖然沒有明說, 不過從測試用例也可以看出)。 因此一個思路就是中序遍歷, 邊遍歷邊改變指針即可。 這里有兩個注意點: 1. 指針操作小心死循環 2. 你需要返回的是最左下角的節點,而不是題目給的 root 對于第一個問題, 其實只要注意操作指針的順序即可。對于第二個問題,我用了一個黑科技,讓代碼看起來簡潔又高效。如果不懂的話, 你也可以換個樸素的寫法。 讓我們進入正題。 其中綠色是我們要增加的連線,而黑色是是原本的連線。 ![](https://img.kancloud.cn/c1/f7/c1f718ed3bcadadd1378001463a8d308_962x492.jpg) 我們再來看一個復雜一點的: ![](https://img.kancloud.cn/18/07/1807112e14db006078677c94b717e2a6_1300x798.jpg) 實際上,不管多么復雜。 我們只需要進行一次**中序遍歷**,同時記錄前驅節點。然后操作修改前驅節點和當前節點的指針即可,整個過程就好像是鏈表反轉。 核心代碼(假設 pre 我們已經正確計算出了): ``` <pre class="calibre18">``` cur.left = <span class="hljs-keyword">None</span> pre.right = cur pre = cur ``` ``` 剩下的就是如何計算 pre,這個也不難,直接看代碼: ``` <pre class="calibre18">``` self.pre = <span class="hljs-keyword">None</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(root)</span>:</span> dfs(root.left) <span class="hljs-title"># 上面的指針改變邏輯寫到這里</span> self.pre = root dfs(root.right) ``` ``` 問題得以解決。 這里還有最后一個問題就是返回值,題目要返回的實際上是最左下角的值。而我用了一個黑科技的方法(注意看注釋): ``` <pre class="calibre18">``` self.pre = self.ans = TreeNode(<span class="hljs-params">-1</span>) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(root)</span>:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root: <span class="hljs-keyword">return</span> dfs(root.left) root.left = <span class="hljs-keyword">None</span> self.pre.right = root <span class="hljs-title"># 當第一次執行到下面這一行代碼,恰好是在最左下角, 這個時候 self.pre = root 就切斷了 self.pre 和 self.ans 的聯系</span> <span class="hljs-title"># 之后 self.pre 的變化都不會體現到 self.ans 上。</span> <span class="hljs-title"># 直觀上來說就是 self.ans 在遍歷到最左下角的時候下車了</span> <span class="hljs-title"># 因此最后返回 self.ans 即可</span> self.pre = root dfs(root.right) dfs(root) <span class="hljs-keyword">return</span> self.ans.right ``` ``` ## 關鍵點 - 指針操作 - 返回值的處理 ## 代碼 ``` <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">convertBiNode</span><span class="hljs-params">(self, root)</span>:</span> self.pre = self.ans = TreeNode(<span class="hljs-params">-1</span>) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dfs</span><span class="hljs-params">(root)</span>:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root: <span class="hljs-keyword">return</span> dfs(root.left) root.left = <span class="hljs-keyword">None</span> self.pre.right = root self.pre = root dfs(root.right) dfs(root) <span class="hljs-keyword">return</span> self.ans.right ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N),其中 N 為樹的節點總數。 - 空間復雜度:O(h)O(h)O(h),其中 h 為樹的高度。 ## 相關題目 - [206.reverse-linked-list](206.reverse-linked-list.html) - [92.reverse-linked-list-ii](92.reverse-linked-list-ii.html) - [25.reverse-nodes-in-k-groups-cn](25.reverse-nodes-in-k-groups-cn.md) 大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的 LeetCode 題解 ![](https://img.kancloud.cn/7b/b1/7bb115b82aa493e2d2a88f71d5201779_1190x680.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>

                              哎呀哎呀视频在线观看