【面試高頻題】二叉樹(shù)"神級(jí)遍歷"入門(mén)

## 題目描述 這是 LeetCode 上的 **[99. 恢復(fù)二叉搜索樹(shù)](https://leetcode.cn/problems/recover-binary-search-tree/solutions/2431878/gong-shui-san-xie-yi-ti-shuang-jie-di-gu-4po4/)** ，難度為 **中等**。 Tag : 「二叉樹(shù)」、「樹(shù)的搜索」、「遞歸」、「迭代」、「中序遍歷」、「Morris 遍歷」 給你二叉搜索樹(shù)的根節(jié)點(diǎn) `root`，該樹(shù)中的 恰好 兩個(gè)節(jié)點(diǎn)的值被錯(cuò)誤地交換。請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹(shù) 。 示例 1： ![](https://upload-images.jianshu.io/upload_images/1980848-1f5507f8e90b4f4e.png) ``` 輸入：root = [1,3,null,null,2] 輸出：[3,1,null,null,2] 解釋?zhuān)? 不能是 1 的左孩子，因?yàn)?3 > 1 。交換 1 和 3 使二叉搜索樹(shù)有效。 ``` 示例 2： ![](https://upload-images.jianshu.io/upload_images/1980848-88aa110592752ba6.png) ``` 輸入：root = [3,1,4,null,null,2] 輸出：[2,1,4,null,null,3] 解釋?zhuān)? 不能在 3 的右子樹(shù)中，因?yàn)?2 < 3 。交換 2 和 3 使二叉搜索樹(shù)有效。 ``` 提示： * 樹(shù)上節(jié)點(diǎn)的數(shù)目在范圍 $[2, 1000]$ 內(nèi) * $-2^{31} <= Node.val <= 2^{31} - 1$ 進(jìn)階：使用 $O(n)$ 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。你能想出一個(gè)只使用 $O(1)$ 空間的解決方案嗎？ ## 基本分析 首先，別想復(fù)雜了。 所謂的恢復(fù)二叉樹(shù)（兩節(jié)點(diǎn)互換），只需要將兩節(jié)點(diǎn)的 `val` 進(jìn)行互換即可，而不需要對(duì)節(jié)點(diǎn)本身進(jìn)行互換。 ## 中序遍歷 - 遞歸 & 迭代 二叉搜索樹(shù)，其中序遍歷是有序的。 要找到哪兩個(gè)節(jié)點(diǎn)被互換，可通過(guò)比對(duì)中序遍歷序列來(lái)實(shí)現(xiàn)。 但將整個(gè)中序遍歷序列保存下來(lái)，再檢測(cè)序列有序性的做法，復(fù)雜度是 $O(n)$ 的（不要說(shuō)題目要求的 $O(1)$，連 $O(h)$ 都達(dá)不到）。 所以第一步，**這個(gè)「遞歸 & 迭代」的次優(yōu)解，我們先考慮如何做到 $O(h)$ 的空間復(fù)雜度，即在中序遍歷過(guò)程中找到互換節(jié)點(diǎn)**。 其實(shí)也很簡(jiǎn)單，除了使用 `a` 和 `b` 來(lái)記錄互換節(jié)點(diǎn)，額外使用變量 `last` 來(lái)記錄當(dāng)前遍歷過(guò)程中的前一節(jié)點(diǎn)即可： 若存在前一節(jié)點(diǎn) `last` 存在，而且滿(mǎn)足前一節(jié)點(diǎn)值大于當(dāng)前節(jié)點(diǎn)（`last.val > root.val`），違反“有序性”，根據(jù)是否為首次出現(xiàn)該情況分情況討論： * 若是首次滿(mǎn)足條件，即 `a == null`，此時(shí)上一節(jié)點(diǎn) `last` 必然是兩個(gè)互換節(jié)點(diǎn)之一，而當(dāng)前 `root` 只能說(shuō)是待定，因?yàn)橛锌赡苁?`last` 和 `root` 實(shí)現(xiàn)互換，也有可能是 `last` 和后續(xù)的某個(gè)節(jié)點(diǎn)實(shí)現(xiàn)互換。 此時(shí)有 `a = last, b = root` * 若是非首次滿(mǎn)足條件，即 `a != null`，此時(shí)當(dāng)前節(jié)點(diǎn) `root` 必然是兩個(gè)互換節(jié)點(diǎn)中的另外一個(gè)。 此時(shí)有 `b = root` 綜上：如果整個(gè)中序遍歷的序列中“逆序?qū)Α睘橐粚?duì)，那么互換節(jié)點(diǎn)為該“逆序?qū)Α钡膬蓚€(gè)成員；若“逆序?qū)Α睌?shù)量為兩對(duì)，則互換節(jié)點(diǎn)為「第一對(duì)“逆序?qū)Α钡氖讉€(gè)節(jié)點(diǎn)」和「第二對(duì)“逆序?qū)Α钡牡诙€(gè)節(jié)點(diǎn)」。 Java 代碼（遞歸）： ```Java class Solution { TreeNode a = null, b = null, last = null; public void recoverTree(TreeNode root) { dfs(root); int val = a.val; a.val = b.val; b.val = val; } void dfs(TreeNode root) { if (root == null) return ; dfs(root.left); if (last != null && last.val > root.val) { if (a == null) { a = last; b = root; } else { b = root; } } last = root; dfs(root.right); } } ``` Java 代碼（迭代）： ```Java class Solution { public void recoverTree(TreeNode root) { Deque d = new ArrayDeque<>(); TreeNode a = null, b = null, last = null; while (root != null || !d.isEmpty()) { while (root != null) { d.addLast(root); root = root.left; } root = d.pollLast(); if (last != null && last.val > root.val) { if (a == null) { a = last; b = root; } else { b = root; } } last = root; root = root.right; } int val = a.val; a.val = b.val; b.val = val; } } ``` * 時(shí)間復(fù)雜度：$O(n)$ * 空間復(fù)雜度：$O(h)$，其中 $h$ 為樹(shù)高 ## 中序遍歷 - Morris 遍歷 Morris 遍歷也就是經(jīng)常說(shuō)到的“神級(jí)遍歷”，其本質(zhì)是通過(guò)做大常數(shù)來(lái)降低空間復(fù)雜度。 還是以二叉樹(shù)的中序遍歷為例，無(wú)論是遞歸或是迭代，為了在遍歷完左節(jié)點(diǎn)（也可以是左子樹(shù)）時(shí)，仍能回到父節(jié)點(diǎn)，我們需要使用數(shù)據(jù)結(jié)構(gòu)棧，只不過(guò)在遞歸做法中是用函數(shù)調(diào)用充當(dāng)棧，而在迭代做法則是顯式棧。 **這使得空間復(fù)雜度為 $O(h)$，而 Morris 遍歷的核心則是利用“路徑底部節(jié)點(diǎn)”中的空閑指針進(jìn)行線(xiàn)索。** 舉個(gè) ??，對(duì)于一棵最簡(jiǎn)單的二叉樹(shù)： ![](https://upload-images.jianshu.io/upload_images/1980848-d0bf8e109b79a0c6.png) 在中序遍歷過(guò)程中，如果選擇遞歸或迭代方式，并且不使用棧的情況，當(dāng)遍歷完左子節(jié)點(diǎn)（或左子樹(shù)的最后一個(gè)節(jié)點(diǎn)）后，將會(huì)面臨無(wú)法返回根節(jié)點(diǎn)的問(wèn)題。 在 Morris 遍歷中，從根節(jié)點(diǎn)開(kāi)始，尚未真正遍歷左子節(jié)點(diǎn)之前，就會(huì)先建立「左子節(jié)點(diǎn)（或左子樹(shù)的最后一個(gè)節(jié)點(diǎn)）」與「當(dāng)前根節(jié)點(diǎn)」之間的鏈接，從而避免使用棧。 具體的，Morris 遍歷的中序遍歷遵循如下流程（喜歡的話(huà)可以背過(guò)）： 1. 令根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn) 2. 只要當(dāng)前節(jié)點(diǎn)不為空（`while (root != null) `），重復(fù)執(zhí)行如下流程： * 若當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)為空（`root.left = null`），將當(dāng)前節(jié)點(diǎn)更新為其右子節(jié)點(diǎn)（`root = root.right`) * 若當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空，利用臨時(shí)變量 `t` 存儲(chǔ)，找到當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)（左子樹(shù)中最后一個(gè)節(jié)點(diǎn)）： * 若前驅(qū)節(jié)點(diǎn)的右子節(jié)點(diǎn)為空（`t.right = null`），將前驅(qū)節(jié)點(diǎn)的右子節(jié)點(diǎn)鏈接到當(dāng)前節(jié)點(diǎn)（`t.right = root`），并將當(dāng)前節(jié)點(diǎn)更新為左子節(jié)點(diǎn)（`root = root.left`） * 若前驅(qū)節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空，說(shuō)明已鏈接到當(dāng)前節(jié)點(diǎn)，此時(shí)將前驅(qū)節(jié)點(diǎn)的右子節(jié)點(diǎn)置空（刪除鏈接 `t.right = null`），遍歷當(dāng)前節(jié)點(diǎn)，并將當(dāng)前節(jié)點(diǎn)更新為右子節(jié)點(diǎn)（`root = root.right`） Java 代碼： ```Java class Solution { public void recoverTree(TreeNode root) { TreeNode a = null, b = null, last = null; while (root != null) { if (root.left == null) { if (last != null && last.val > root.val) { if (a == null) { a = last; b = root; } else { b = root; } } last = root; root = root.right; } else { TreeNode t = root.left; while (t.right != null && t.right != root) t = t.right; if (t.right == null) { // 若前驅(qū)節(jié)點(diǎn)右子樹(shù)為空, 說(shuō)明是真正遍歷左子樹(shù)前, 建立與當(dāng)前根節(jié)點(diǎn)的鏈接, 然后開(kāi)始真正遍歷左子樹(shù) t.right = root; root = root.left; } else { // 若已存在鏈接, 說(shuō)明是第二次訪(fǎng)問(wèn)根節(jié)點(diǎn), 左子樹(shù)（前驅(qū)節(jié)點(diǎn)）已遍歷完, 此時(shí)應(yīng)該解開(kāi)鏈接, 遍歷當(dāng)前節(jié)點(diǎn)以及右子樹(shù) t.right = null; if (last != null && last.val > root.val) { if (a == null) { a = last; b = root; } else { b = root; } } last = root; root = root.right; } } } int val = a.val; a.val = b.val; b.val = val; } } ``` * 時(shí)間復(fù)雜度：$O(n)$ * 空間復(fù)雜度：$O(1)$ ## 最后 這是我們「刷穿 LeetCode」系列文章的第 `No.99` 篇，系列開(kāi)始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。 在這個(gè)系列文章里面，除了講解解題思路以外，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼。如果涉及通解還會(huì)相應(yīng)的代碼模板。 為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼，我建立了相關(guān)的倉(cāng)庫(kù)：https://github.com/SharingSource/LogicStack-LeetCode 。 在倉(cāng)庫(kù)地址里，你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解。 更多更全更熱門(mén)的「筆試/面試」相關(guān)資料可訪(fǎng)問(wèn)排版精美的 [合集新基地](https://www.acoier.com/archives/) ????
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容