# 面試題 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 對于第一個問題， 其實只要注意操作指針的順序即可。對于第二個問題，我用了一個黑科技，讓代碼看起來簡潔又高效。如果不懂的話， 你也可以換個樸素的寫法。 讓我們進入正題。 其中綠色是我們要增加的連線，而黑色是是原本的連線。  我們再來看一個復雜一點的：  實際上，不管多么復雜。 我們只需要進行一次**中序遍歷**，同時記錄前驅節點。然后操作修改前驅節點和當前節點的指針即可，整個過程就好像是鏈表反轉。 核心代碼（假設 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 題解