【面试高频题】二叉树"神级遍历"入门

## 题目描述这是 LeetCode 上的 **[99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree/solutions/2431878/gong-shui-san-xie-yi-ti-shuang-jie-di-gu-4po4/)** ，难度为 **中等**。 Tag : 「二叉树」、「树的搜索」、「递归」、「迭代」、「中序遍历」、「Morris 遍历」给你二叉搜索树的根节点 `root`，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。示例 1： ![](https://upload-images.jianshu.io/upload_images/1980848-1f5507f8e90b4f4e.png) ``` 输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。 ``` 示例 2： ![](https://upload-images.jianshu.io/upload_images/1980848-88aa110592752ba6.png) ``` 输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。 ``` 提示： * 树上节点的数目在范围 $[2, 1000]$ 内 * $-2^{31} <= Node.val <= 2^{31} - 1$ 进阶：使用 $O(n)$ 空间复杂度的解法很容易实现。你能想出一个只使用 $O(1)$ 空间的解决方案吗？ ## 基本分析首先，别想复杂了。所谓的恢复二叉树（两节点互换），只需要将两节点的 `val` 进行互换即可，而不需要对节点本身进行互换。 ## 中序遍历 - 递归 & 迭代二叉搜索树，其中序遍历是有序的。要找到哪两个节点被互换，可通过比对中序遍历序列来实现。但将整个中序遍历序列保存下来，再检测序列有序性的做法，复杂度是 $O(n)$ 的（不要说题目要求的 $O(1)$，连 $O(h)$ 都达不到）。所以第一步，**这个「递归 & 迭代」的次优解，我们先考虑如何做到 $O(h)$ 的空间复杂度，即在中序遍历过程中找到互换节点**。其实也很简单，除了使用 `a` 和 `b` 来记录互换节点，额外使用变量 `last` 来记录当前遍历过程中的前一节点即可：若存在前一节点 `last` 存在，而且满足前一节点值大于当前节点（`last.val > root.val`），违反“有序性”，根据是否为首次出现该情况分情况讨论： * 若是首次满足条件，即 `a == null`，此时上一节点 `last` 必然是两个互换节点之一，而当前 `root` 只能说是待定，因为有可能是 `last` 和 `root` 实现互换，也有可能是 `last` 和后续的某个节点实现互换。此时有 `a = last, b = root` * 若是非首次满足条件，即 `a != null`，此时当前节点 `root` 必然是两个互换节点中的另外一个。此时有 `b = root` 综上：如果整个中序遍历的序列中“逆序对”为一对，那么互换节点为该“逆序对”的两个成员；若“逆序对”数量为两对，则互换节点为「第一对“逆序对”的首个节点」和「第二对“逆序对”的第二个节点」。 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; } } ``` * 时间复杂度：$O(n)$ * 空间复杂度：$O(h)$，其中 $h$ 为树高 ## 中序遍历 - Morris 遍历 Morris 遍历也就是经常说到的“神级遍历”，其本质是通过做大常数来降低空间复杂度。还是以二叉树的中序遍历为例，无论是递归或是迭代，为了在遍历完左节点（也可以是左子树）时，仍能回到父节点，我们需要使用数据结构栈，只不过在递归做法中是用函数调用充当栈，而在迭代做法则是显式栈。 **这使得空间复杂度为 $O(h)$，而 Morris 遍历的核心则是利用“路径底部节点”中的空闲指针进行线索。** 举个 🌰，对于一棵最简单的二叉树： ![](https://upload-images.jianshu.io/upload_images/1980848-d0bf8e109b79a0c6.png) 在中序遍历过程中，如果选择递归或迭代方式，并且不使用栈的情况，当遍历完左子节点（或左子树的最后一个节点）后，将会面临无法返回根节点的问题。在 Morris 遍历中，从根节点开始，尚未真正遍历左子节点之前，就会先建立「左子节点（或左子树的最后一个节点）」与「当前根节点」之间的链接，从而避免使用栈。具体的，Morris 遍历的中序遍历遵循如下流程（喜欢的话可以背过）： 1. 令根节点为当前节点 2. 只要当前节点不为空（`while (root != null) `），重复执行如下流程： * 若当前节点的左子节点为空（`root.left = null`），将当前节点更新为其右子节点（`root = root.right`) * 若当前节点的左子节点不为空，利用临时变量 `t` 存储，找到当前节点的前驱节点（左子树中最后一个节点）： * 若前驱节点的右子节点为空（`t.right = null`），将前驱节点的右子节点链接到当前节点（`t.right = root`），并将当前节点更新为左子节点（`root = root.left`） * 若前驱节点的右子节点不为空，说明已链接到当前节点，此时将前驱节点的右子节点置空（删除链接 `t.right = null`），遍历当前节点，并将当前节点更新为右子节点（`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) { // 若前驱节点右子树为空, 说明是真正遍历左子树前, 建立与当前根节点的链接, 然后开始真正遍历左子树 t.right = root; root = root.left; } else { // 若已存在链接, 说明是第二次访问根节点, 左子树（前驱节点）已遍历完, 此时应该解开链接, 遍历当前节点以及右子树 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; } } ``` * 时间复杂度：$O(n)$ * 空间复杂度：$O(1)$ ## 最后这是我们「刷穿 LeetCode」系列文章的第 `No.99` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。更多更全更热门的「笔试/面试」相关资料可访问排版精美的 [合集新基地](https://www.acoier.com/archives/) 🎉🎉

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,772评论 6赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,458评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,610评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,640评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,657评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,590评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,962评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,631评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,870评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,611评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,704评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,386评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,969评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,944评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,179评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,742评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,440评论 2赞 342

【面试高频题】二叉树"神级遍历"入门

推荐阅读更多精彩内容