作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你二叉搜索树的根节点 root，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。
输入格式
- root：二叉树的根节点。
输出格式
- 不需要返回值，直接在原树上进行恢复。
示例
示例 1
输入: [1,3,null,null,2] 输出: [3,1,null,null,2] 解释: 3 和 1 被错误交换。
示例 2
输入: [3,1,4,null,null,2] 输出: [2,1,4,null,null,3] 解释: 2 和 3 被错误交换。
方法一：中序遍历和交换
解题步骤
- 中序遍历：使用中序遍历找到两个错误的节点。
- 节点交换：找到两个不符合中序递增顺序的节点后，交换它们的值。
完整的规范代码
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def recoverTree(root): """ 使用中序遍历恢复二叉搜索树 :param root: TreeNode, 二叉搜索树的根节点 """ stack = [] x = y = prev = None while stack or root: while root: stack.append(root) root = root.left root = stack.pop() if prev and root.val < prev.val: y = root if not x: x = prev else: break prev = root root = root.right # 交换两个节点的值 if x and y: x.val, y.val = y.val, x.val # 示例调用 root = TreeNode(1, TreeNode(3, None, TreeNode(2))) recoverTree(root)
算法分析
- 时间复杂度：(O(n))，需要遍历所有节点。
- 空间复杂度：(O(h))，其中 (h) 是树的高度，用于存储栈。
中序遍历的 ASCII 图解
假设我们有一个二叉树，其中两个节点值被错误交换，例如树结构为：
3 / \ 1 4 / 2
中序遍历应为 [1, 3, 4, 2]，但正确的排序应为 [1, 2, 3, 4]，其中 4 和 2 被错误地交换。
开始中序遍历： 访问节点 3 | 去左 -> 访问节点 1 | | 打印节点 1 | | 返回节点 3 | 打印节点 3 | 去右 -> 访问节点 4 | | 去左 -> 访问节点 2 | | | 打印节点 2 | | | 返回节点 4 | | 打印节点 4 | | 结束
方法二：Morris 中序遍历
解题步骤
- Morris 遍历：这种遍历方式不需要额外的空间，通过修改树的结构实现。
- 找出并交换错误节点：在遍历过程中寻找顺序错误的节点，并在遍历结束后交换它们的值。
完整的规范代码
def recoverTree(root): x = y = prev = pred = None while root: if root.left: pred = root.left while pred.right and pred.right != root: pred = pred.right if not pred.right: pred.right = root root = root.left else: if prev and root.val < prev.val: y = root if not x: x = prev prev = root pred.right = None root = root.right else: if prev and root.val < prev.val: y = root if not x: x = prev prev = root root = root.right if x and y: x.val, y.val = y.val, x.val # 示例调用 root = TreeNode(1, TreeNode(3, None, TreeNode(2))) recoverTree(root)
算法分析
- 时间复杂度：(O(n))，虽然是 Morris 遍历，每个节点最多被访问两次。
- 空间复杂度：(O(1))，不使用额外空间，除非修改了树的结构。
不同算法的优劣势对比
| 特征 | 方法一：中序遍历 | 方法二：Morris 遍历 |
| 时间复杂度 | (O(n)) | (O(n)) |
| 空间复杂度 | (O(h)) | (O(1)) |
| 优势 | 易于理解和实现 | 不需要额外空间 |
| 劣势 | 空间复杂度较高 | 修改了树的结构 |
Morris 遍历的 ASCII 图解
使用同样的树结构进行 Morris 遍历，我们通过修改树的结构来避免使用额外的空间。
开始Morris遍历： 访问节点 3 | 左节点存在，找到前驱（节点 1） | | 前驱的右节点为空，链接到当前节点 | | 去左 | 访问节点 1 | | 前驱是节点 3，断开链接，打印节点 1 | | 返回节点 3，打印节点 3 | 去右 -> 访问节点 4 | | 左节点存在，找到前驱（节点 2） | | | 前驱的右节点为空，链接到当前节点 | | | 去左 | | 访问节点 2 | | | 前驱是节点 4，断开链接，打印节点 2 | | | 返回节点 4，打印节点 4 | | 结束
应用示例
这些方法可用于数据库中维护数据索引的完整性、修复由于错误操作或系统故障导致数据结构损坏的情况，或者在进行复杂的数据操作前验证数据的一致性。
欢迎关注微信公众号 数据分析螺丝钉
